差分|树上差分学习笔记|P3128 [USACO15DEC]最大流Max Flow题解

[【树上差分模板题】](https://www.luogu.org/problemnew/show/P3128) 矩阵的差分应该很简单，典型题目是这样的： 给你一堆数，有n次修改操作，每次给i..j这个区间加上x。最后问所有数中最大的那个。 差分，通俗一点就是把区间的操作改为点操作，在点上记录变化量。上题只需记录dlt[i]+=x,dlt[j+1]-=x，最后用前缀和扫一遍即可。 树上差分，顾名思义就是在树上搞差分。有两种典型题型，一种是边差分，一种是点差分。边差分裸题长这样： 给你一棵树，有n次修改操作，每次把u..v的路径权值加x，最后问从x..y的路径权值和。  例如有一次操作是把红点（u）到绿点（v）之间的路径全部加x。那么我就标记dlt[u]+=x,dlt[v]+=x。  这样在最后求解的时候，回溯的时候顺便算一下答案就出来了。 然后我们要在lca(u,v)处标记dlt[lca(u,v)]-=2x。这样就使得加x的效果只局限在u..v，不会向lca(u,v)的爸爸蔓延。 点差分和边差分稍有差别： 有n次修改操作，每次把u..v的所有点权都加x，最后问点权最大的为多少。这道题就是最上方链接的那题了。 做法也是和边差分稍有不同，我们不在dlt[lca(u,v)]-=2x，而是把dlt[lca(u,v)]-=x并把dlt[fa[lca(u,v)]]-=x。为什么呢？因为lca(u,v)也在u..v这条路径上，它同样需要被加x。回溯的时候会从u和v两个方向都给lca(u,v)加一个x，而它只能加一个，因此dlt[lca(u,v)]-=x。而lca(u,v)的爸爸则根本无法被加，在lca(u,v)已经只加一个x了，因此dlt[fa[lca(u,v)]]-=x就能让lca(u,v)的爸爸不加x。 具体看代码： ``` #include<bits/stdc++.h> #define fsb(a,b,c) for (int a=b;a<=c;a++) #define maxn 50100 #define maxm 100100 #define mem(a,b) memset(a,b,sizeof(a)) #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; struct edge{ int p,nt; }a[maxn*2]; int n,m,x,y,head[maxn],cnt=0,cntb=0,headb[maxn],fa[maxn],vis[maxn],dlt[maxn],faa[maxn],maxx=0; struct qus{ int p,nt,mark; }b[maxm*2]; struct ablca{ int x,y,z; }ans[maxm]; inline void adda(int x,int y){ a[++cnt].p=y;a[cnt].nt=head[x];head[x]=cnt; } inline void addb(int x,int y,int z){ b[++cntb].p=y;b[cntb].mark=z;b[cntb].nt=headb[x];headb[x]=cntb; } inline int getf(int x){ return x==fa[x]?x:fa[x]=getf(fa[x]); } inline void dfs1(int u,int f){//tarjan求lca faa[u]=f; for (int t=headb[u];t!=-1;t=b[t].nt){ int v=b[t].p; if (vis[v]) ans[b[t].mark].z=getf(v); } // printf("%d ",u); vis[u]=1; for (int t=head[u];t!=-1;t=a[t].nt){ int v=a[t].p;if (v==f) continue; dfs1(v,u); int fau=getf(u),fav=getf(v); if (fau!=fav) fa[fav]=fau; } } inline int dfs2(int u){ int now=dlt[u],ans=0; for (int t=head[u];t!=-1;t=a[t].nt){ int v=a[t].p;if (v==faa[u]) continue; now+=dfs2(v);//now记录点u的修改后点权 } maxx=max(maxx,now); return now; } int main(){ // freopen("std.in","r",stdin); scanf("%d%d",&n,&m); mem(head,255); fsb(i,1,n-1){ scanf("%d%d",&x,&y);adda(x,y);adda(y,x); } mem(headb,255); fsb(i,1,m){ scanf("%d%d",&ans[i].x,&ans[i].y); addb(ans[i].x,ans[i].y,i);addb(ans[i].y,ans[i].x,i); } fsb(i,1,n) fa[i]=i;mem(vis,0); dfs1(1,0);mem(dlt,0); fsb(i,1,m){ dlt[ans[i].x]++;dlt[ans[i].y]++;dlt[ans[i].z]--;dlt[faa[ans[i].z]]--; } // printf("!!!\n"); n=dfs2(1); printf("%d\n",maxx); return 0; } ``` 差分适用于修改多而询问少的情况，本题中只有一次询问，非常适合【别和我说线段树，树链剖分，LCT云云，赛场上写了1个小时调了1个小时结果炸了岂不心态要崩orz一定是我太菜了调不出来orz