差分
如果去看我的树状数组的博客的话就懂了，就是记录相邻节点值的差值。这样一来，前缀和就相当于原值了。
树上差分
树上差分基本上就是差分在树上的实现。因为差分的原理，我们先将所有点的权值改变成差分值，再更改一段区间内的所有值时，只需要更改首尾两端的值，如果要求值的话dfs重新加上前缀和就是正常的值了。
模板题，发现更改任意两点间的值只需要在两点差分值加上1然后在lca和fa[lca]（倍增的话就是fa[lca][0]）上减去1，从根dfs并记录最大值即可。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<ctype.h> #define R register using namespace std; inline int read() { int x=0,w=0;char c=getchar(); while(!isdigit(c))w|=c==‘-‘,c=getchar(); while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); return w?-x:x; } const int maxn=233333; int n,m,ans[maxn]; int top[maxn],fa[maxn][18],dep[maxn],head[maxn],ecnt,cnt; struct Edge{ int to,nxt; }e[maxn<<1]; inline void addedge(int a,int b) { e[++ecnt]=(Edge){b,head[a]};head[a]=ecnt; e[++ecnt]=(Edge){a,head[b]};head[b]=ecnt; } bool vis[maxn]; void dfs1(int x,int depth) { for (R int i=0;fa[x][i];++i) fa[x][i+1]=fa[fa[x][i]][i]; vis[x]=1; dep[x]=depth; for(R int i=head[x];i;i=e[i].nxt) { int u=e[i].to; if(vis[u])continue; fa[u][0]=x; dfs1(u,depth+1); } } inline int LCA(int u,int v) { if(dep[u]<dep[v])swap(u,v); for(R int i=0;i<=16;i++) if((dep[u]-dep[v])&(1<<i))u=fa[u][i]; if(u==v)return u; for(R int i=16;i>=0;i--) if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int Ans=0; void dfs2(int x) { vis[x]=1; for(R int i=head[x];i;i=e[i].nxt) { int u=e[i].to; if(vis[u])continue; dfs2(u); ans[x]+=ans[u]; } Ans=max(Ans,ans[x]); } int main() { n=read(),m=read(); for(R int i=1;i<n;i++)addedge(read(),read()); fa[1][0]=0; dfs1(1,1); for(R int i=1;i<=m;i++) { int x=read(),y=read(); int lca=LCA(x,y); ans[x]++,ans[y]++,ans[lca]--,ans[fa[lca][0]]--; } memset(vis,0,sizeof vis); dfs2(1); printf("%d\n",Ans); return 0; }
原文：https://www.cnblogs.com/BrotherHood/p/13200165.html