2704: 秋静叶 & 秋穣子
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
在幻想乡，秋姐妹是掌管秋天的神明，作为红叶之神的姐姐静叶和作为丰收之神的妹妹穰子。如果把红叶和果实联系在一起，自然会想到烤红薯。烤红薯需要很多的叶子，才能把红薯烤得很香，所以秋姐妹决定比比谁能够收集到最多的红叶。静叶将红叶分成了N堆(编号1..N)，并且规定了它们的选取顺序，刚好形成一颗有向树。在游戏过程中，两人从根节点开始，轮流取走红叶，当一个人取走节点i的红叶后，另一个人只能从节点i的儿子节点中选取一个。当取到某个叶子时游戏结束，然后两人会比较自己得到的红叶数量。已知两人采用的策略不一样，静叶考虑在让穰子取得尽可能少的前提下，自己取的最多；而穰子想得是在自己尽可能取得多的前提下，让静叶取得最少。在两人都采取最优策略的情况下，请你计算出游戏结束时两人的红叶数量。
游戏总是静叶先取，保证只存在一组解。
输入
第1行：1个正整数N，表示红叶堆数
第2行：N个整数，第i个数表示第i堆红叶的数量num[i]
第3..N+1行：2个正整数u,v，表示节点u为节点v的父亲
输出
第1行：2个整数，分别表示静叶取到的叶子数和穰子取到的叶子数
样例输入 复制
6
4 16 16 5 3 1
1 2
2 4
1 3
3 5
3 6样例输出 复制
7 16提示
首先静叶一定能取得节点1的4片红叶，留给穰子的是节点2和3，均为16片红叶。若选取节点2则静叶下一次可以最多得到5片红叶，而选择3静叶最多也只能得到3片红叶，所以此时穰子会选择节点3，故静叶最后得到的红叶数为7，穰子为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
保证两人得到的红叶数在[0, 2^31-1]。