题意
有一颗(n)个节点的树，还有(m)条路径
统计一个节点作为第(a_i)个在路径中被经过的点（从(0)开始算）的个数
思路
首先有一个想法，一条路径中从上到下和从下到上一个是递减一个是递增，那么他们与他们的深度有什么关系呢？
上行：深度越小，到达名次越大(f[i]=deep[s]-deep[i])
下行：深度越小，到达名次越小(f[i]=(deep[i]-deep[lca])+(deep[s]-deep[lca])=deep[i]+deep[s]-2deep[lca])
那么一条路径中的名次就可以用点本身的深度和一些定值来表示，树上差分就可以派上用场了
对于上行和下行分别处理：
- 上行对于路径上的点都打上(deep[s])的标记
- 下行则打上(deep[s]-2deep[lca])的标记
查询时只需查询(a[i]-deep[i])即可
接着怎么样统计？线段树合并大法好。不要打错就好，处理一些越界如小于(0)，大于(n)的都没有意义。
#include <bits/stdc++.h>
using std::swap;
const int N=300005;
int f[N][20],tree[2][N*80],l[2][N*80],r[2][N*80],n,m,x,y,to[N<<1],last[N],Next[N<<1],edge,rt[2][N*20],ans[N],d[N],a[N],cnt[2];
void add(int x,int y){
to[++edge]=y;
Next[edge]=last[x];
last[x]=edge;
}
void dfs(int x,int fa,int deep){
f[x][0]=fa,d[x]=deep;
for (int i=last[x];i;i=Next[i])
if (to[i]!=fa)
dfs(to[i],x,deep+1);
}
int change(int flag,int k,int L,int R,int x,int val){
if (!k) k=++cnt[flag];
if (L==R){
tree[flag][k]+=val;
return k;
}
int mid=(L+R)>>1;
if (x>mid) r[flag][k]=change(flag,r[flag][k],mid+1,R,x,val);
else l[flag][k]=change(flag,l[flag][k],L,mid,x,val);
tree[flag][k]=tree[flag][l[flag][k]]+tree[flag][r[flag][k]];
return k;
}
int lca(int x,int y){
if (d[x]<d[y]) swap(x,y);
for (int i=18;i>=0;i--) if (d[f[x][i]]>=d[y]) x=f[x][i];
if (x==y) return x;
for (int i=18;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int merge(int flag,int L,int R,int x,int y){
if (!x) return y;
if (!y) return x;
if (L==R){
tree[flag][x]+=tree[flag][y];
return x;
}
int mid=(L+R)>>1;
l[flag][x]=merge(flag,L,mid,l[flag][x],l[flag][y]);
r[flag][x]=merge(flag,mid+1,R,r[flag][x],r[flag][y]);
tree[flag][x]=tree[flag][l[flag][x]]+tree[flag][r[flag][x]];
return x;
}
int query(int flag,int L,int R,int k,int x){
if (k==0 || x>R) return 0;
if (L==R) return tree[flag][k];
int mid=(L+R)>>1;
if (x<=mid) return query(flag,L,mid,l[flag][k],x);
else return query(flag,mid+1,R,r[flag][k],x);
}
void dfs2(int x,int fa){
for (int i=last[x];i;i=Next[i])
if (to[i]!=fa){
dfs2(to[i],x);
rt[1][x]=merge(1,1,n,rt[1][x],rt[1][to[i]]);
rt[0][x]=merge(0,1,3*n,rt[0][x],rt[0][to[i]]);
}
ans[x]=query(1,1,n,rt[1][x],d[x]+a[x])+query(0,1,3*n,rt[0][x],a[x]+2*n-d[x]);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,0,1);
for (int i=1;i<=18;i++)
for (int j=1;j<=n;j++) f[j][i]=f[f[j][i-1]][i-1];
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
int l=lca(x,y);
rt[1][x]=change(1,rt[1][x],1,n,d[x],1);
if (f[l][0]) rt[1][f[l][0]]=change(1,rt[1][f[l][0]],1,n,d[x],-1);
rt[0][y]=change(0,rt[0][y],1,3*n,d[x]-2*d[l]+2*n,1);
rt[0][l]=change(0,rt[0][l],1,3*n,d[x]-2*d[l]+2*n,-1);
}
dfs2(1,0);
for (int i=1;i<=n;i++) printf("%d ",ans[i]);
}
途中把(L)打成了(1)，调了好久，还是太菜了
update 2019.8
发现根本不用什么线段树合并。我在写什么鬼东东。一个(dfs)就好