洛谷 P3128 [ USACO15DEC ] 最大流Max Flow —— 树上差分

时间:2022-09-07 22:42:57

题目:https://www.luogu.org/problemnew/show/P3128

倍增求 lca 也写错了活该第一次惨WA。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=;
int n,m,hd[maxn],ct,f[maxn][],dep[maxn],s[maxn],mx;
bool vis[maxn];
struct N{
int to,nxt;
N(int t=,int n=):to(t),nxt(n) {}
}ed[maxn<<];
void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}
void dfs0(int x,int fa)
{
f[x][]=fa; dep[x]=dep[fa]+;
for(int i=;i<;i++)f[x][i]=f[f[x][i-]][i-];
for(int i=hd[x],u;i;i=ed[i].nxt)
{
if((u=ed[i].to)==fa)continue;
dfs0(u,x);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
// for(int i=18;i>=0;i--)
// if(dep[f[x][i]]>dep[y])x=f[x][i];
// x=f[x][0];
int t=dep[x]-dep[y];
for(int i=;i>=;i--)
if(t&(<<i))x=f[x][i];
for(int i=;i>=;i--)
// if(dep[f[x][i]]!=dep[f[y][i]])x=f[x][i],y=f[y][i];
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
if(x==y)return x;
return f[x][];
}
void dfs(int x)
{
for(int i=hd[x],u;i;i=ed[i].nxt)
{
if((u=ed[i].to)==f[x][])continue;
dfs(u);
s[x]+=s[u];
}
mx=max(mx,s[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs0(,);
for(int i=,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
int l=lca(x,y);
s[x]++; s[y]++; s[l]--; s[f[l][]]--;
}
dfs();
printf("%d\n",mx);
return ;
}