【NOIP2016】天天爱跑步

题面

分析

上次用树链剖分写了一次..现在回头重新来看，就感觉到树上差分真的是好东西了。

这个题在树上差分里面level已经很高了，但是其实还是蛮套路的，和普通的树上差分区分度就在于每个点有个观察时间w[u]

然而比较温情的是出发时间都是确定的，从一开始就出发，且边权为1.

于是我们可以发现有两种情况可以链接这个w[u]

  1. 存在点x处于s到lca的路上（包括lca），则有dep[s]-dep[x]=w[x]，移项得dep[s]=w[x]+dep[x]
  2. 存在点x处于lca到t的路上（为避免重复计算不包括lca），则有dep[s]+dep[x]-2*dep[lca]=w[x]，移项得dep[s]-2*dep[lca]=w[x]-dep[x]。

稍微解释一下这两个式子，每个等式移项前的左右两边都表示s-->x的距离（因为边权为1，所以距离也等于时间）

于是，我们需要在每个s-->t的路径中找到有多少个满足条件的x即可。

为什么可以差分？因为标记影响到的仅仅是以lca为根的这棵子树，符合树上差分的答案是子树和的思想。

而我们只需要计算以某点为根的子树在累积答案前后的差值，就可以得到这个点的答案。

具体做法：当我们遇到每一组s和t时，就映射等式左边部分，打上标记，在dfs过程中查询映射等式右边部分的数量。

即通过已知的dep[s]和dep[lca]加标记，而在dfs过程中w也变为已知量，再引入w求解。

需要注意的是lca不能重复计算，一个删除标记打在lca的父亲上，另一个要打在lca上。

再次提醒，别用map，这玩意儿常数神大，读入输出优化，inline，register都救不了。上次做分块的时候就已经被map教做人了。

而且这题貌似卡常？？我把map映射改成数组映射过后那个被卡T的点直接跑成600ms...

代码

  1. #include<bits/stdc++.h>  
  2. using namespace std;  
  3. #define N 300030  
  4. #define RT register   
  5. int n,m,cnt;  
  6. int d[N],w[N],dep[N],ans[N],first[N],fa[N][20];  
  7. int A[N*10],B[N*10];  
  8. struct email  
  9. {  
  10.     int u,v;  
  11.     int nxt;  
  12. }e[N*4];  
  13. struct update  
  14. {  
  15.     int c,tag,id;  
  16. };  
  17. vector<update>v[N];  
  18. template<class T>  
  19. inline void read(T &x)  
  20. {  
  21.     x=0;int f=1;static char c=getchar();   
  22.     while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}  
  23.     while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}  
  24.     x*=f;  
  25. }  
  26.   
  27. void print(int x)  
  28. {  
  29.     if(x>9)print(x/10);  
  30.     putchar(x%10+'0');  
  31. }  
  32.   
  33. inline void add(int u,int v)  
  34. {  
  35.     e[++cnt].nxt=first[u];first[u]=cnt;  
  36.     e[cnt].u=u;e[cnt].v=v;  
  37. }  
  38. inline void pre(int u,int f)  
  39. {  
  40.     for(RT int i=1;(1<<i)<=dep[u];++i)  
  41.         fa[u][i]=fa[fa[u][i-1]][i-1];  
  42.     for(RT int i=first[u];i;i=e[i].nxt)  
  43.     {  
  44.         int v=e[i].v;  
  45.         if(v==f)continue;  
  46.         dep[v]=dep[u]+1;  
  47.         fa[v][0]=u;  
  48.         pre(v,u);  
  49.     }  
  50. }  
  51.   
  52. inline int lca(int x,int y)  
  53. {  
  54.     if(dep[x]<dep[y])swap(x,y);  
  55.     int t=dep[x]-dep[y];  
  56.     for(RT int i=0;(1<<i)<=t;++i)  
  57.         if((1<<i)&t)  
  58.             x=fa[x][i];  
  59.     if(x==y)return x;  
  60.     for(RT int i=19;i>=0;--i)  
  61.         if(fa[x][i]!=fa[y][i])  
  62.             x=fa[x][i],y=fa[y][i];  
  63.     return fa[x][0];  
  64. }   
  65.   
  66. inline void dfs(int u,int f)  
  67. {  
  68.     int st1=A[w[u]+dep[u]],st2=B[w[u]-dep[u]+n];  
  69.     for(RT int i=first[u];i;i=e[i].nxt)  
  70.     {  
  71.         int v=e[i].v;  
  72.         if(v==f)continue;  
  73.         dfs(v,u);  
  74.     }  
  75.     for(RT int i=0;i<v[u].size();i++)  
  76.     {  
  77.         update x=v[u][i];  
  78.         if(x.c==1)A[x.id]+=x.tag;  
  79.         else B[x.id+n]+=x.tag;  
  80.     }  
  81.     ans[u]=A[w[u]+dep[u]]+B[w[u]-dep[u]+n]-st1-st2;  
  82. }  
  83.   
  84.   
  85. int main()  
  86. {  
  87.     read(n);read(m);  
  88.     for(RT int i=1;i<n;++i)  
  89.     {  
  90.         int u,v,w;  
  91.         read(u),read(v);  
  92.         add(u,v);add(v,u);  
  93.     }   
  94.     pre(1,0);  
  95.     for(RT int i=1;i<=n;++i)read(w[i]);  
  96.     for(RT int i=1;i<=m;++i)  
  97.     {  
  98.         int s,t,LCA;  
  99.         read(s),read(t);LCA=lca(s,t);  
  100.         v[s].push_back({1,1,dep[s]});v[fa[LCA][0]].push_back({1,-1,dep[s]});  
  101.         v[t].push_back({2,1,dep[s]-2*dep[LCA]});v[LCA].push_back({2,-1,dep[s]-2*dep[LCA]});  
  102.     }  
  103.     dfs(1,0);  
  104.     for(RT int i=1;i<=n;++i)print(ans[i]),putchar(' ');  
  105.     return 0;  
  106. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/NSD-email0820/p/9855227.html