题解 P3128 【[USACO15DEC]最大流Max Flow】

这题，首先应该看出这是一棵树。。。 其次，才是 LCA+树上差分 的算法。。。 树上差分的核心是：起点++，终点++，LCA（起点，终点）--，father[ LCA（起点，终点） ]-- LCA 建议用倍增，因为要用到 LCA 的 父亲（本人不会用 Tarjan 同时求 LCA 与 LCA 的父亲，吃枣药丸）。。。 如果上述算法还是看不懂，还有最后一招，上代码！！！ 附注释的代码： ```cpp #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 100010//防止 MLE using namespace std; int n,m,ans=0,c=1; int head[MAXN<<1],f[MAXN][20],deep[MAXN],s1[MAXN],s2[MAXN]; struct node{ int next,to; }a[MAXN<<1];//前向星存图 inline int read(){//读优。。。 int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } void add(int x,int y){//在 x 与 y 之间加入一条双向边 a[c].to=y; a[c].next=head[x]; head[x]=c++; a[c].to=x; a[c].next=head[y]; head[y]=c++; } void buildtree(int rt){//建树，顺便处理了 每个节点的深度 与 每个节点的父亲 。。。 int will; for(int i=head[rt];i;i=a[i].next){ will=a[i].to;//每条边的终点 if(!deep[will]){ deep[will]=deep[rt]+1; f[will][0]=rt; buildtree(will);//遍历子节点（当初就是因为手残，将 will 敲成了 rt ，瞬间爆炸，于是调了半小时。。。） } } } void step(){//跳跃步数 for(int i=1;i<=19;i++) for(int j=1;j<=n;j++) f[j][i]=f[f[j][i-1]][i-1];//倍增思想应该都理解吧。。。 } int LCA(int x,int y){//求LCA if(deep[x]<deep[y])swap(x,y);//总是将 x 设为深度较深的节点 for(int i=19;i>=0;i--)//将 x 与 y 拉至同一深度 if(deep[f[x][i]]>=deep[y]) x=f[x][i]; if(x==y)return x; for(int i=19;i>=0;i--)//寻找深度比 LCA大1 的节点 if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i]; } return f[x][0];//返回 深度比 LCA大1 的节点 的上一层，即LCA } void work(int x,int y){//差分 int fa=LCA(x,y); s1[x]++;s1[y]++;s1[fa]--; if(f[fa][0]!=0)s1[f[fa][0]]--; } void getsum(int now,int rt){//求出每个节点的压力。。。 int t; s2[now]=s1[now]; for(int i=head[now];i;i=a[i].next){ t=a[i].to; if(t!=rt){ getsum(t,now); s2[now]+=s2[t]; } } ans=max(ans,s2[now]);//比较大小并更新。。。 } int main(){//主函数 So easy! int x,y; n=read();m=read(); for(int i=1;i<n;i++){ x=read();y=read(); add(x,y);//建边 s1[i]=deep[i]=0;//表示不想用 memset,已经被坑过无数次。。。 } deep[1]=1; buildtree(1); step(); while(m--){ x=read();y=read(); work(x,y); } getsum(1,0); printf("%d\n",ans);//输出答案。。。 return 0;//结束，撒花~~~ } ```