Description：

Solution1：

Solution2：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

struct edge

{

	int to,nxt,f;

}e[MAXN * 12];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int f)

{//cout << a << " " << b << " " << f << endl;

	e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

	return;

}

int ind[MAXN];

#define INF 0x3f3f3f3f

int s,t,ss,tt;

int ch[MAXN];

bool BFS()

{

    memset(ch,-1,sizeof(ch));ch[s] = 0;

    queue<int> q;q.push(s);

    while(!q.empty())

    {

        int k = q.front();q.pop();

        for(int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(ch[e[i].to] == -1 && e[i].f)

            {

                ch[e[i].to] = ch[k] + 1;

                q.push(e[i].to);

            }

        }

    }

    return (ch[t] != -1);

}

int cur[MAXN];

int flow(int k,int f)

{

    if(k == t)return f;

    int r = 0;

    for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

    {

        if(ch[e[i].to] == ch[k] + 1 && e[i].f)

        {

            int l = flow(e[i].to,min(e[i].f,f - r));

            e[i].f -= l;r += l;e[i ^ 1].f += l;

        }

        lin[k] = i;

    }

    if(r == 0)ch[k] = -1;

    return r;

}

#define INF 0x3f3f3f3f

int dinic()

{

    int ans = 0,r;

    memcpy(cur,lin,sizeof(lin));

    while(BFS())

	{

		ans += flow(s,INF);

		memcpy(lin,cur,sizeof(lin));

	}//cout << ans << endl;

    return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	int a,b; 

	for(int i = 1;i < n;++i)

	{

		a = rd();b = rd();

		++a;++b;

		add(b,a,INF);

		++ind[a];--ind[b];

	}

	ss = n + 1;tt = n + 2;s = n + 3;t = n + 4;

	for(int i = 1;i <= n;++i)add(ss,i,INF),add(i,tt,INF);

	for(int i = 1;i <= n;++i)

	{

		if(ind[i] > 0)add(s,i,ind[i]);

		if(ind[i] < 0)add(i,t,-ind[i]);

	}

	dinic();

	add(tt,ss,INF);

	cout << dinic() << endl;

	return 0;

}