链接一下题目：luoguP3128 [USACO15DEC]最大流Max Flow(树上差分板子题)
如果没有学过树上差分,抠这里(其实很简单的,真的):树上差分总结
学了树上差分,这道题就极其显然了,不就是把每一条运输路线差分进去,那就是板子了啊.
树上差分还是很有用的,比较容易写,这种询问很少的题目去敲那么长(还容易出玄学错误)的树剖很浪费,用树上差分就很快了!(//...微笑...\\)
上一波代码:
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iomanip> #include<ctime> #include<queue> #include<stack> #define rg register #define lst long long #define N 50050 using namespace std;int n,K,cnt,ans; struct EDGE{int to,nxt; }edge[N<<1]; int head[N]; int fa[N],v[N],deep[N]; int f[N][25];inline int read() {rg int s=0,m=1;rg char ch=getchar();while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')m=-1,ch=getchar();while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();return s*m; }inline void add(rg int p,rg int q) {edge[++cnt]=(EDGE){q,head[p]};head[p]=cnt; }void dfs(rg int now,rg int fm,rg int dep)//点,父亲,深度 {fa[now]=fm;deep[now]=dep;f[now][0]=fa[now];for(rg int i=1;i<=20;++i)f[now][i]=f[f[now][i-1]][i-1];for(rg int i=head[now];i;i=edge[i].nxt){rg int qw=edge[i].to;if(qw!=fm)dfs(qw,now,dep+1);} }inline int lca(rg int p,rg int q) {if(deep[p]<deep[q])swap(p,q);while(deep[p]>deep[q])for(rg int i=20;i>=0;--i)if(deep[f[p][i]]>=deep[q])p=f[p][i];while(p!=q){for(rg int i=20;i>=0;--i)if(f[p][i]!=f[q][i])p=f[p][i],q=f[q][i];if(fa[p]==fa[q])p=q=fa[p];}if(p==q)return p; }inline void Insert(rg int p,rg int q)//如模板,差分 {v[p]++,v[q]++;//自己++rg int LCA=lca(p,q); // printf("lca(%d,%d)=%d\n",p,q,LCA);v[LCA]--,v[fa[LCA]]--;//LCA和fa[LCA]-- }void sum(rg int now) {for(rg int i=head[now];i;i=edge[i].nxt){rg int qw=edge[i].to;if(qw!=fa[now]){sum(qw);v[now]+=v[qw];}}ans=max(ans,v[now]); }int main() {n=read(),K=read();for(rg int i=1;i<n;++i){rg int p=read(),q=read();add(p,q),add(q,p);}dfs(1,0,1);//倍增的预处理 // for(rg int i=\1;i<=n;++i)cout<<deep[i]<<" ";cout<<endl; /* for(rg int i=1;i<=n;++i){for(rg int j=0;j<=2;j++){printf("f[%d][%d]=%d ",i,j,f[i][j]);}cout<<endl;}cout<<endl;*/for(rg int i=1;i<=K;++i){rg int p=read(),q=read();Insert(p,q);//差分 }add(0,1);//0上面也会有标记,所以上面的东西也要弄掉sum(0);//dfs遍历顺便找答案printf("%d\n",ans);return 0; }