2200专项：E. Demiurges Play Again（思维 树上）

原题： http://codeforces.com/problemset/problem/538/E

题意：

一棵1为根的树，设叶子节点的个数为x，那么你现在可以将叶子编号为1~x。之后两个人开始做游戏，从根开始，两个人依次选择一个儿子，跳到儿子上，最后落在一个叶子上得分为其编号。第一个人想要得分大，第二个人小。问你怎么样排编号使之最大最小。

解析：

先来看最大的

看15号点，由第二个人控制。如果目标答案在15这个点产生，需要消耗3个点（第二个人会选16，17，18中小的，所以要用三个点，产生了第3大的结果）

看8号点，由第一个人控制。13和14只需要一个点即可（将13或14附为最大值，第一个人会直接选），而走15号最大只能选第3大，所以8号点的答案为1。

总结：

由第二个人控制的，对儿子的答案累加。而第一个人，在儿子中选min。最大值为第（1节点答案）大的数。

再看最小值，15号的三个儿子中放一个最小的即可，所以答案为1。8号点要想取到最小值，要放3个（第一个人无视较小的）。

所以和上面是相反的，第一个人累加，第二个人取min。此时为第（1节点答案）小的数。

#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int maxn=2e5+5;
vector<int> V[maxn];
int son=0;
int dfs(int p,int fa,bool f){
    if(f){
        int res=1e9;
        for(int i=0;i<V[p].size();i++){
            int u=V[p][i];
            if(u==fa)continue;
            int val=dfs(u,p,!f);
            res=min(res,val);
        }
        if(res==1e9)return 0*(++son)+1;
        return res;
    }
    else{
        int res=0;
        for(int i=0;i<V[p].size();i++){
            int u=V[p][i];
            if(u==fa)continue;
            int val=dfs(u,p,!f);
            res+=val;
        }
        if(res==0)return 0*(++son)+1;
        return res;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    int ma=dfs(1,-1,1);
    int mi=dfs(1,-1,0);
    printf("%d %d\n",son/2-ma+1,mi);
}