P1600 天天爱跑步
分析：
首先若想对于每一个人统计他的路线对观察点的贡献，显然是很难优化到log的。
考虑对每一个观察点统计答案。
一个观察点会被这样两种路径经过：
1.起点在其下方，从起点向上走经过它。
2.终点在其下方，从某一处的起点向下走经过它。
对于第一种情况，我们要满足：dep[ s ] == dep[ x ] + w[ x ]（x是观察点，就是说s在x点的下面，过了w[ x ]秒正好到达x点）
对于第二种情况，我们要满足：tim=dep[ s ] + dep[ t ] - 2*dep[ lc ]（从s到t经过的时间） tim - （dep[ t ] - dep[ x ]） == w[ x ]（总体花费的时间-从x走下来到 t 花费的时间，就是从s走到x花费的时间）
第二种化简一下：dep[ s ] - 2 * dep [ lc ] == w[ x ] - dep[ x ]
两种情况后半部分都只与观察点有关，当一个观察点x的子树中，有满足以上两个等式就将ans[ x ]++。
所以我们只需要对上面左边的式子开一个桶记录一下即可。
但是会出现起点终点都在x一下，从头到尾都不经过x的，怎么办呢？
树上差分！
对于第一种，在fa[ lc ]上的桶减去贡献即可。
对于第二种，在lc上的桶减去贡献。（为什么不是fa[ lc ]：lc已经归结在第一种情况里面了，在第二种的半路径里是不包括lc的！！）
但还有一个问题：统计子树的时候他们是共用一个桶，信息重复了怎么办？
设u的两个子节点v1和v2。
当v1遍历完后，桶中保留了v1及其所有子节点的信息。
这时我们遍历v2，将v2子树中的信息也加入桶里，那么统计v2的贡献时明显会统计到v1子树中的，怎么办呢？
只需要在将v2子树中信息加入前记录一下原来的，然后加入后再两者相减即可。
#include<bits/stdc++.h> using namespace std; #define N 300005 #define ri register int vector<int> a1[N],a2[N],b1[N*3],b2[N*3],e[N]; int sum1[N<<1],sum2[N<<1],fa[N][22],w[N],n,m,ans[N],dep[N]; void dfs1(int u,int ff) { for(ri i=0;i<e[u].size();++i){ int v=e[u][i]; if(v==ff) continue; fa[v][0]=u; dep[v]=dep[u]+1; for(ri j=1;j<=20;++j) fa[v][j]=fa[fa[v][j-1]][j-1]; dfs1(v,u); } } int lca(int a,int b) { if(dep[a]<dep[b]) swap(a,b); for(ri i=20;i>=0;--i) if(dep[fa[a][i]]>=dep[b]) a=fa[a][i]; if(a==b) return a; for(ri i=20;i>=0;--i) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i]; return fa[a][0]; } void dfs2(int u,int ff) { int tmp1=sum1[dep[u]+w[u]],tmp2=sum2[w[u]-dep[u] +n]; for(ri i=0;i<e[u].size();++i) if(e[u][i]!=ff) dfs2(e[u][i],u); for(ri i=0;i<a1[u].size();++i) sum1[a1[u][i]]++; for(ri i=0;i<a2[u].size();++i) sum1[a2[u][i]]--; for(ri i=0;i<b1[u].size();++i) sum2[b1[u][i]]++; for(ri i=0;i<b2[u].size();++i) sum2[b2[u][i]]--; ans[u]=sum1[dep[u]+w[u]]-tmp1 + sum2[w[u]-dep[u] +n]-tmp2; } int main() { scanf("%d%d",&n,&m); int a,b; for(ri i=1;i<=n-1;++i) scanf("%d%d",&a,&b),e[a].push_back(b),e[b].push_back(a); dep[0]=-1; dep[1]=0; dfs1(1,0); for(ri i=1;i<=n;++i) scanf("%d",&w[i]); for(ri i=1;i<=m;++i){ int s,t; scanf("%d%d",&s,&t); int lc=lca(s,t); a1[s].push_back(dep[s]);//a1是加的桶，记录标记，dfs的时候再释放 a2[fa[lc][0]].push_back(dep[s]);//a2是减的桶 b1[t].push_back(dep[s]-2*dep[lc] +n);//防止越界 b2[lc].push_back(dep[s]-2*dep[lc] +n); } dfs2(1,0); for(ri i=1;i<=n;++i) printf("%d ",ans[i]); } /* 6 3 2 3 1 2 1 4 4 5 4 6 0 2 5 1 2 3 1 5 1 3 2 6 5 3 1 2 2 3 2 4 1 5 0 1 0 3 0 1 4 3 1 5 5 */