http://codeforces.com/problemset/problem/538/E
题目大意：
给出一棵树，叶子节点上都有一个值，从1-m。有两个人交替从根选择道路，先手希望到达的叶子节点尽量大，后手希望到达的叶子节点尽量小，叶子节点的放置方案任意。两个人都足够聪明，能够得到的最大值和最小值分别是多少。
思路:
先考虑最大的情况
考虑dp[i]代表i这个节点能达到的最大的数字在这个子树中排第几。
如果当前是先手操作，那么他肯定会往最大的那个子树的方向走，即dp[u]=min(dp[v])
如果当前是后手操作，那么他肯定往最小的走，即dp[u]=Σdp[v]，这样就走到了最差子树的最大数字去了。
然后最小的情况类似
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
int tot,go[],next[],first[];
int n,f1[],f2[],pd[],son[],deep[];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void add(int x,int y){
insert(x,y);
insert(y,x);
}
void dfs(int x,int fa){
int pdd=;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa) continue;
pdd=;
deep[pur]=deep[x]+;
dfs(pur,x);
son[x]+=son[pur];
}
if (!pdd) son[x]=,pd[x]=;
}
void dfs1(int x,int fa){
if (pd[x]==) {
f1[x]=;
return;
}
if (deep[x]%){
f1[x]=0x7fffffff;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa) continue;
dfs1(pur,x);
f1[x]=std::min(f1[x],f1[pur]);
}
}else{
f1[x]=;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa) continue;
dfs1(pur,x);
f1[x]+=f1[pur];
}
}
}
void dfs2(int x,int fa){
if (pd[x]==) {
f2[x]=;
return;
}
if (deep[x]%){
f2[x]=;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa) continue;
dfs2(pur,x);
f2[x]+=f2[pur];
}
}else{
f2[x]=0x7fffffff;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa) continue;
dfs2(pur,x);
f2[x]=std::min(f2[x],f2[pur]);
}
}
}
int main(){
n=read();
for (int i=;i<n;i++){
int x=read(),y=read();
add(x,y);
}
deep[]=;
dfs(,);
dfs1(,);
printf("%d ",son[]-f1[]+);
dfs2(,);
printf("%d\n",f2[]);
return ;
}