网络流建图。
从S向每个点连边，从每个点向T连边。
每条树边反向连一条下界为1，上界inf的边。
跑最小流。
注意加当前弧优化。
#include<cstdio>
#include<algorithm>
#define inf 0x3f3f3f3f
#define N 500005
#define M 5000005
using namespace std;
int head[N],ver[M],nxt[M],f[M],tot,ch[N],cur[M];
void add(int a,int b,int c)
{
tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;f[tot]=c;
tot++;nxt[tot]=head[b];head[b]=tot;ver[tot]=a;f[tot]=0;
return ;
}
int S,T,tim;
int vis[100005],q[M];
bool tell()
{
tim++;
int l=1,r=1;q[1]=S;
ch[S]=0;vis[S]=tim;
while(l<=r)
{
int tmp=q[l++];
for(int i=head[tmp];i;i=nxt[i])
{
if(f[i]&&vis[ver[i]]!=tim)
{
ch[ver[i]]=ch[tmp]+1;
vis[ver[i]]=tim;
q[++r]=ver[i];
}
}
}
return vis[T]==tim;
}
int zeng(int a,int b)
{
if(a==T)return b;
int r=0;
for(int i=cur[a];i&&b>r;i=nxt[i])
{
if(ch[ver[i]]==ch[a]+1&&f[i])
{
int t=zeng(ver[i],min(b-r,f[i]));
r+=t;f[i]-=t;f[i^1]+=t;
if(f[i]>0)cur[a]=i;
}
}
if(!r)ch[a]=-1;
return r;
}
int dinic()
{
int r=0,t;
while(tell())
{
for(int i=0;i<=T;i++)cur[i]=head[i];
while(t=zeng(S,inf))r+=t;
}
return r;
}
int n;
int ru[N],chu[N];
int main()
{
scanf("%d",&n);int t1,t2;
tot=1;
for(int i=1;i<n;i++)
{
scanf("%d%d",&t1,&t2);
t1++;t2++;
ru[t2]++;chu[t1]++;
add(t1,t2,inf);
}
int TT=n+1,SS=0;
for(int i=1;i<=n;i++)
{
add(SS,i,inf);add(i,TT,inf);
}
S=n+2;T=n+3;
for(int i=1;i<=n;i++)
{
if(chu[i]>ru[i])
{
add(i,T,chu[i]-ru[i]);
}
else if(ru[i]>chu[i])
{
add(S,i,ru[i]-chu[i]);
}
}
dinic();
add(TT,SS,inf);
dinic();
printf("%d\n",f[tot]);
return 0;
}