【题解】Luogu P1600 天天爱跑步 LCA+树上差分
真·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 }
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 }