【题目描述】
RHL 有一天看到 lmc 在玩一个游戏。
“愚蠢的人类哟，what are you doing”，RHL 说。
“我在玩一个游戏。现在这里有一个有 n 个结点的有根树，其中有 m 个叶子结点。这 m
个叶子从 1 到 m 分别被给予了一个号码，每个叶子的号码都是独一无二的。一开始根节点有
一个棋子，两个玩家每次行动将棋子移动到当前节点的一个儿子节点。当棋子被移动到某个
叶节点的时候游戏结束，这个叶节点的号码即为该局游戏的 result。先手的玩家要最大化
result，后手的玩家要最小化这个 result。”
“你不先问一下我是谁吗 = =”
“那么，who are you”
“我是这个世界的创造者，维护者和毁灭者，整个宇宙的主宰，无所不知，无所不能的，
三个字母都大写的 RHL。”
“既然你这么厉害，那你一定知道，在两个玩家都无限聪明的情况下，在树的形态已知
的情况下，在叶子的编号可以任意安排的情况下，游戏的 result 最大是多少咯。”
【输入格式】
输入数据第一行有一个正整数 n，表示结点的数量。
接下来 n-1 行，每行有两个正整数 u 和 v，表示的父亲节点是 u。
【输出格式】
输出一行 2 个非负整数，分别表示 result 的最大值和最小值。
【样例输入】
5
1 2
1 3
2 4
2 5
【样例输出】
3 2
【样例解释】
有 3,4,5 三个叶子。若令 3 号叶子的编号是 3，则先手可以移到 3 号结点，故 result
最大是 3。若 3 号叶子的编号是 2，则先手可以移到 3 号结点，故 result 最小是 2.
【数据范围】
30%，n<=10
100%,n<=200000
一道tree DP题·····
只考虑最大值的情况，即为A来编号。
设sum[u]表示以u为根的子树有sum[u]个叶子节点，f[u]表示A先手时的最好方案，g[u]表示B先手时的最好方案
对于f[u]，设v为u的儿子，则f[u]=max( sum[u]-(sum[v]-g[v]+1)+1 )
对于g[u]，则g[u]=sum[u]-sigma(sum[v]-f[v]+1)+1
最小值同理
code：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 200005
#define inf maxn+10
using namespace std;
int n,a,b,tot,root,now[maxn],son[maxn],pre[maxn],sum[maxn],f[maxn][],g[maxn][];
bool bo[maxn],ok[maxn];
void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
void dfs(int u){
if (!bo[u]){f[u][]=f[u][]=g[u][]=g[u][]=sum[u]=;return;}
for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]) dfs(v),sum[u]+=sum[v];
int s1=,s2=;
for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]){
f[u][]=max(f[u][],sum[u]-sum[v]+g[v][]);
g[u][]=min(g[u][],f[v][]);
s1+=sum[v]-f[v][]+,s2+=g[v][];
}
g[u][]=sum[u]-s1+,f[u][]=s2;
}
int main(){
freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
scanf("%d",&n);
for (int i=;i<n;i++) scanf("%d%d",&a,&b),put(a,b),bo[a]=,ok[b]=;
for (int i=;i<=n;i++) if (!ok[i]) root=i;
for (int i=;i<=n;i++) g[i][]=inf;
dfs(root);
printf("%d %d\n",f[root][],f[root][]);
return ;
}