树上差分（CF 191C）

树上差分有两种（其实也可以说是前缀和）： 一种是用来统计一条边被覆盖了多少次。对于树上的一条路径u，v，我们可以把它拆成u->Lca,v->Lca。我们和处理线性的差分一样，让c[u]++,c[Lca]--,c[v]++,c[Lca]--（c为差分数组）。这样就可以表示出u->v这条路径的覆盖次数+1。统计的时候，对于一条边，它被覆盖的次数，就是下端端点这颗子树的c数组值之和。 另一种就是点的差分，也就是求点被覆盖了几次。基本操作相同，只是在处理c数组时，对于路径u->v，我们让c[u]++,c[v]++,c[Lca]--,c[fa[Lca]]--。原因是u->v这条路径覆盖了Lca，而边差分时并没有覆盖Lca作为下端点的边。 对于这道题，自然是边差分模板。。 ------------ ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,k,cnt=0; int head[501000],nxt[501000],to[501000]; int d[501000],f[25][501000],num[501000]; int p[501000]; struct Edge { int x,y; }e[501000]; void addedge(int x,int y) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; } void dfs(int u,int dep) { d[u]=dep,p[++cnt]=u; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(!d[v]) f[0][v]=u,dfs(v,dep+1); } } int Lca(int x,int y) { if(d[x]<d[y]) swap(x,y); for(int i=20;i>=0;i--) if(d[f[i][x]]>=d[y]) x=f[i][x]; if(x==y) return x; for(int i=20;i>=0;i--) if(f[i][x]!=f[i][y]) { x=f[i][x]; y=f[i][y]; } return f[0][x]; } int main() { memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); e[i].x=x,e[i].y=y; } f[0][1]=0; cnt=0; dfs(1,1); for(int i=1;i<=20;i++) for(int j=1;j<=n;j++) f[i][j]=f[i-1][f[i-1][j]]; scanf("%d",&k); for(int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); num[x]++,num[y]++,num[Lca(x,y)]-=2; } for(int i=n;i>=1;i--) num[f[0][p[i]]]+=num[p[i]]; for(int i=1;i<n;i++) { if(d[e[i].x]<d[e[i].y]) e[i].x=e[i].y;//利用深度数组，得到这条边的下端点 printf("%d ",num[e[i].x]); } return 0; } ```