Description
话说前年Alice和Bob相聚在一起玩游戏后，彼此都很忙，因此很少见面。今年由于为了NOIP2011又再次相聚，他们俩还是想比比谁能够收集到最多的石子数量。Alice将石子分成了N堆（编号1..N），并且规定了它们的选取顺序，刚好形成一颗有向树。在游戏过程中，两人从根节点开始，轮流取走石子，当一个人取走节点i的石子后，另一个人只能从节点i的儿子节点中选取一个。当取到某个叶子时游戏结束，然后两人会比较自己得到的石子数量。已知两人采用的策略不一样，Alice考虑在让Bob取得尽可能少的前提下，自己取的最多；而Bob想得是在自己尽可能取得多的前提下，让Alice取得最少。在两人都采取最优策略的情况下，请你计算出游戏结束时两人的石子数量。
游戏总是Alice先取，保证只存在一组解。
Input
第1行只有一个正整数N，表示石子堆数；
第2行包含N个整数，第i个数表示第i堆石子的数量num[i]；
第3..N+1行，每行两个正整数u和v，表示节点u为节点v的父亲；
Output
输出文件仅一行为两个整数，分别表示Alice取到的石子数和Bob取到的石子数。
Sample Input
6
4 16 16 5 3 1
1 2
2 4
1 3
3 5
3 6
Sample Output
7 16
Hint
【样例解释】
首先Alice一定能取得节点1的4个石子，留给Bob的是节点2和3，均为16个石子。若选取节点2则Alice下一次可以最多得到5个石子，而选择3，则Alice最多也只能得到3个石子，所以此时Bob会选择节点3，故Alice最后得到的石子数为7，Bob为16。
【数据范围】
对于30%的数据，1≤N≤100，1≤num[i]≤100；
对于60%的数据，1≤N≤10,000，1≤num[i]≤10,000
对于100%的数据，1≤N≤100,000，1≤num[i]≤10,000
思路
- 个人觉得这个写法还是
比较反人类的，参考此blog的思路和代码更好理解
代码
#include <iostream>
#include <cstdio>
#define maxn 100005
using namespace std;
int n,v[maxn],cnt,head[maxn],sum[2][maxn],din[maxn],k;
struct fdfdfd{int next,to;}e[maxn];
void addedge(int x,int y){e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;}
void dfs(int x,int dep)
{//dp[0][i]表示以i为根先手能获得的叶子数量，dp[1][i]表示以i为根后手能获得的叶子数量。
for(int i=head[x],flag=0;i;i=e[i].next)
{
int y=e[i].to; dfs(y,dep+1);
if(flag)
{
if(dep&1)
{
if(sum[0][y]>sum[0][x]) sum[0][x]=sum[0][y],sum[1][x]=sum[1][y];
if(sum[0][y]==sum[0][x]) sum[1][x]=min(sum[1][y],sum[1][x]);
}
else
{
if(sum[0][y]<sum[0][x]) sum[0][x]=sum[0][y],sum[1][x]=sum[1][y];
if(sum[0][y]==sum[0][x]) sum[1][x]=max(sum[1][y],sum[1][x]);
}
}
else
{
sum[0][x]=sum[0][y],sum[1][x]=sum[1][y];
flag=1;
}
}
sum[dep&1][x]+=v[x];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&v[i]);
for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),addedge(u,v),++din[v];
for(int i=1;i<=n;++i)//找root
if(!din[i]){k=i; dfs(i,1); break;}
printf("%d %d",sum[1][k],sum[0][k]);
return 0;
}