真·NOIp day1 T2

众所周知noip按难度顺序出题

感谢洛谷题解@greenlcat 提供思路及写法

写+调+写题解 共计一整个晚上2.5个小时对我今天晚自习啥都没干

分步解决这个题

Step 1 :倍增LCA

本身这题码量就不小,还写树剖LCA,我这个菜鸡调不出来的

倍增求LCA好像没什么可写的,基本操作

 1 int n,m,cnt,deep[maxn],fa[maxn][25],w[maxn],head[maxn];
 2 struct edge{
 3     int nxt,to;
 4 }e[maxn*2];
 5 inline void add(int from,int to){
 6     e[++cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;
 7 }
 8 void dfs1(int x){
 9     for(int i=1;(1<<i)<=deep[x];i++){
10         fa[x][i]=fa[fa[x][i-1]][i-1];
11     }
12     for(int i=head[x];i;i=e[i].nxt){
13         int y=e[i].to;
14         if(y==fa[x][0])continue;
15         fa[y][0]=x;
16         deep[y]=deep[x]+1;
17         dfs1(y);
18     }
19 }
20 int lca(int x,int y){
21     if(x==y)return x;
22     if(deep[x]<deep[y])swap(x,y);
23     int k=log(deep[x]-deep[y])/log(2);
24     for(int i=k;i>=0;i--){
25         if(deep[fa[x][i]]>=deep[y]){
26             x=fa[x][i];
27         }
28         if(x==y)return x;
29     }
30     k=log(deep[x])/log(2);
31     for(int i=k;i>=0;i--){
32         if(fa[x][i]!=fa[y][i]){
33             x=fa[x][i];y=fa[y][i];
34         }
35     }
36     return fa[x][0];
37 }
38 int main(){
39     n=read();m=read();
40     for(int i=1;i<n;i++){
41         int u,v;u=read();v=read();
42         add(u,v);add(v,u);
43     }
44     deep[1]=1;fa[1][0]=1;dfs1(1);
45     for(int i=1;i<=n;i++){
46         w[i]=read();
47     }
48     return 0;
49 }
part one

Step 2 :分析转化

发现模拟每个玩家的复杂度爆炸,分着不行就考虑整体处理

改为枚举每个观察员,看哪些节点对观察员有贡献(可被观察到)

而枚举观察员可以转化成dfs整棵树,O(n)可以接受

考虑对于一个观察员x,如果他在一条$s_i$到$t_i$的路径上

1.如果x在$s_i$到LCA上

当$s_i$满足$deep[{s_i}]=w[x]+deep[x]$时,$s_i$对x有1的贡献

2.如果x在$t_i$到LCA上

当$t_i$满足$dis[{s_i},{t_i}]-deep[{t_i}]=w[x]-deep[x]$时,$t_i$对x有1的贡献

所以我们发现,能够对x有贡献的$s_i$或$t_i$都在以x为根的子树上

Step 3 :统计贡献

code(注释都在代码里了)

 1 struct edge{
 2     int nxt,to;
 3 }e1[maxn*2],e2[maxn*2];
 4 inline void add1(int from,int to){
 5     e1[++cnt1].to=to;e1[cnt1].nxt=h1[from];h1[from]=cnt1;
 6 }
 7 inline void add2(int from,int to){
 8     e2[++cnt2].to=to;e2[cnt2].nxt=h2[from];h2[from]=cnt2;
 9 }
10 int b1[maxn*2],b2[maxn*2],js[maxn],dis[maxn];
11 int s[maxn],l[maxn],t[maxn],ans[maxn];
12 void dfs2(int x){
13     int t1=b1[w[x]+deep[x]],t2=b2[w[x]-deep[x]+maxn];
14      //递归前先读桶里的数值,t1是上行桶里的值,t2是下行桶的值
15     for(int i=head[x];i;i=e[i].nxt){ //递归子树
16         int y=e[i].to;
17         if(y==fa[x][0])continue;
18         dfs2(y);
19     }
20     b1[deep[x]]+=js[x];
21     //上行过程中,当前点作为路径起点产生贡献,入桶
22     for(int i=h1[x];i;i=e1[i].nxt){
23         //下行过程中,当前点作为路径终点产生贡献,入桶
24         int y=e1[i].to;
25         b2[dis[y]-deep[t[y]]+maxn]++;
26     }
27     ans[x]+=b1[w[x]+deep[x]]-t1+b2[w[x]-deep[x]+maxn]-t2;
28     //计算上、下行桶内差值,累加到ans[x]里面
29     for(int i=h2[x];i;i=e2[i].nxt){
30         //回溯前清除以此结点为LCA的起点和终点在桶内产生的贡献,它们已经无效了
31         int y=e2[i].to;
32         b1[deep[s[y]]]--;
33         b2[dis[y]-deep[t[y]]+maxn]--;
34     }
35 }
36 int main(){
37     for(int i=1;i<=m;i++){
38         s[i]=read();t[i]=read();
39         int lcaa=lca(s[i],t[i]); //求LCA
40         dis[i]=deep[s[i]]+deep[t[i]]-2*deep[lcaa];
41         js[s[i]]++;//统计以s[i]为起点路径的条数
42         add1(t[i],i);//第i条路径加入到以t[i]为终点的路径集合中
43         add2(lcaa,i);//把每条路径归到对应的LCA集合中
44         if(deep[lcaa]+w[lcaa]==deep[s[i]]){
45             //如果路径起点或终点刚好为LCA且LCA处是可观察到运动员的,答案--
46             ans[lcaa]--;
47         }
48     }
49     dfs2(1);
50     for(int i=1;i<=n;i++){
51         printf("%lld ",ans[i]);
52     }
53     return 0;
54 }
part two

完整高清无注释code

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 namespace gengyf{
  4 #define ll long long
  5 #define int long long
  6 const int maxn=3e5+10;
  7 inline int read(){
  8     int x=0,f=1;
  9     char c=getchar();
 10     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 11     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
 12     return x*f;
 13 }
 14 int n,m,cnt,deep[maxn],fa[maxn][25],w[maxn],head[maxn];
 15 int h1[maxn],h2[maxn],cnt1,cnt2;
 16 struct edge{
 17     int nxt,to;
 18 }e[maxn*2],e1[maxn*2],e2[maxn*2];
 19 inline void add(int from,int to){
 20     e[++cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;
 21 }
 22 inline void add1(int from,int to){
 23     e1[++cnt1].to=to;e1[cnt1].nxt=h1[from];h1[from]=cnt1;
 24 }
 25 inline void add2(int from,int to){
 26     e2[++cnt2].to=to;e2[cnt2].nxt=h2[from];h2[from]=cnt2;
 27 }
 28 void dfs1(int x){
 29     for(int i=1;(1<<i)<=deep[x];i++){
 30         fa[x][i]=fa[fa[x][i-1]][i-1];
 31     }
 32     for(int i=head[x];i;i=e[i].nxt){
 33         int y=e[i].to;
 34         if(y==fa[x][0])continue;
 35         fa[y][0]=x;
 36         deep[y]=deep[x]+1;
 37         dfs1(y);
 38     }
 39 }
 40 int lca(int x,int y){
 41     if(x==y)return x;
 42     if(deep[x]<deep[y])swap(x,y);
 43     int k=log(deep[x]-deep[y])/log(2);
 44     for(int i=k;i>=0;i--){
 45         if(deep[fa[x][i]]>=deep[y]){
 46             x=fa[x][i];
 47         }
 48         if(x==y)return x;
 49     }
 50     k=log(deep[x])/log(2);
 51     for(int i=k;i>=0;i--){
 52         if(fa[x][i]!=fa[y][i]){
 53             x=fa[x][i];y=fa[y][i];
 54         }
 55     }
 56     return fa[x][0];
 57 }
 58 int b1[maxn*2],b2[maxn*2],js[maxn],dis[maxn];
 59 int s[maxn],l[maxn],t[maxn],ans[maxn];
 60 void dfs2(int x){
 61     int t1=b1[w[x]+deep[x]],t2=b2[w[x]-deep[x]+maxn];
 62     for(int i=head[x];i;i=e[i].nxt){
 63         int y=e[i].to;
 64         if(y==fa[x][0])continue;
 65         dfs2(y);
 66     }
 67     b1[deep[x]]+=js[x];
 68     for(int i=h1[x];i;i=e1[i].nxt){
 69         int y=e1[i].to;
 70         b2[dis[y]-deep[t[y]]+maxn]++;
 71     }
 72     ans[x]+=b1[w[x]+deep[x]]-t1+b2[w[x]-deep[x]+maxn]-t2;
 73     for(int i=h2[x];i;i=e2[i].nxt){
 74         int y=e2[i].to;
 75         b1[deep[s[y]]]--;
 76         b2[dis[y]-deep[t[y]]+maxn]--;
 77     }
 78 }
 79 int main(){
 80     n=read();m=read();
 81     for(int i=1;i<n;i++){
 82         int u,v;u=read();v=read();
 83         add(u,v);add(v,u);
 84     }
 85     deep[1]=1;fa[1][0]=1;dfs1(1);
 86     for(int i=1;i<=n;i++){
 87         w[i]=read();
 88     }
 89     for(int i=1;i<=m;i++){
 90         s[i]=read();t[i]=read();
 91         int lcaa=lca(s[i],t[i]);
 92         dis[i]=deep[s[i]]+deep[t[i]]-2*deep[lcaa];
 93         js[s[i]]++;
 94         add1(t[i],i);add2(lcaa,i);
 95         if(deep[lcaa]+w[lcaa]==deep[s[i]]){
 96             ans[lcaa]--;
 97         }
 98     }
 99     dfs2(1);
100     for(int i=1;i<=n;i++){
101         printf("%lld ",ans[i]);
102     }
103     return 0;
104 }
105 }
106 signed main(){
107   gengyf::main();
108   return 0;
109 }
View Code

完结撒花花

02-13 20:32