【题目描述】
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：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 200005 6 #define inf maxn+10 7 using namespace std; 8 int n,a,b,tot,root,now[maxn],son[maxn],pre[maxn],sum[maxn],f[maxn][2],g[maxn][2]; 9 bool bo[maxn],ok[maxn]; 10 void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;} 11 void dfs(int u){ 12 if (!bo[u]){f[u][0]=f[u][1]=g[u][0]=g[u][1]=sum[u]=1;return;} 13 for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]) dfs(v),sum[u]+=sum[v]; 14 int s1=0,s2=0; 15 for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]){ 16 f[u][0]=max(f[u][0],sum[u]-sum[v]+g[v][0]); 17 g[u][1]=min(g[u][1],f[v][1]); 18 s1+=sum[v]-f[v][0]+1,s2+=g[v][1]; 19 } 20 g[u][0]=sum[u]-s1+1,f[u][1]=s2; 21 } 22 int main(){ 23 freopen("tree.in","r",stdin),freopen("tree.out","w",stdout); 24 scanf("%d",&n); 25 for (int i=1;i<n;i++) scanf("%d%d",&a,&b),put(a,b),bo[a]=1,ok[b]=1; 26 for (int i=1;i<=n;i++) if (!ok[i]) root=i; 27 for (int i=1;i<=n;i++) g[i][1]=inf; 28 dfs(root); 29 printf("%d %d ",f[root][0],f[root][1]); 30 return 0; 31 }