【th04】秋静叶&秋穣子

2014年3月23日1,6040

Description

在幻想乡,秋姐妹是掌管秋天的神明,作为红叶之神的姐姐静叶和作为丰收之神的妹妹穰子。如果把红叶和果实联系在一起,自然会想到烤红薯。烤红薯需要很多的叶子,才能把红薯烤得很香,所以秋姐妹决定比比谁能够收集到最多的红叶。静叶将红叶分成了N堆(编号1..N),并且规定了它们的选取顺序,刚好形成一颗有向树。在游戏过程中,两人从根节点开始,轮流取走红叶,当一个人取走节点i的红叶后,另一个人只能从节点i的儿子节点中选取一个。当取到某个叶子时游戏结束,然后两人会比较自己得到的红叶数量。
已知两人采用的策略不一样.

在两人都采取最优策略的情况下,请你计算出游戏结束时两人的红叶数量。 游戏总是静叶先取,保证只存在一组解。

 

Input

第1行:1个正整数N,表示红叶堆数
第2行:N个整数,第i个数表示第i堆红叶的数量num[i]
第3..N+1行:2个正整数u,v,表示节点u为节点v的父亲

Output

第1行:2个整数,分别表示静叶取到的叶子数和穰子取到的叶子数

Sample Input

 

 

Sample Output

 

 

Hint

首先静叶一定能取得节点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]。

注意使用手工栈

【分析】

博弈论

在一棵有向树上最大-最小博弈。注意先后手的规则是不一样的。先手尽量让对方取少,而后手尽量让自己取多。注意要记录一个depth,以区分这个点是奇数还是偶数来判断先后手取得,以使用不同的规则。

我们定义一个数组F[MAXN][2],F[i][0]表示以i为根的子树的先手最优值,F[i][1]表示以i为根的子树的后手最优值。

对于depth&1==1的情况:

F[i][0]=Num[i]+F[k][1];

F[i][1]=F[k][0];

k是i的儿子,k为max{F[k][0]}取得最大时的k,F[k][0]相同时,取F[k][1]最小的

即我是先手(全局的先手),我只能取奇数深度的根节点,然后我的对手便会按照他的准则来取。他的准则便是让自己尽量多,所以他会在保证F[k][0](他是全局的后手,那么他便是以k为根子树的先手)最大的情况下,来让F[k][1]最小,即让我尽量少。

 

对于depth&1==0的情况:

同样地:F[i][0]=Num[i]+F[k][1];

F[i][1]=F[k][0];

k是i的儿子,k为min{F[k][1]}取得最小时的k,F[k][1]相同时,取F[k][0]最大的

即我是后手(全局的后手),我只能取偶数深度的根节点,而当前节点深度正好为偶数。我对手的准则让我尽量少,所以他会在保证F[k][1]尽量小的情况下(我是全局后手,又k为奇数节点,所以我为k的后手),让F[k][0]尽量大,即让我的对手尽量多。

这样做可以得九十分,其余俩点会栈溢出

于是我们要手动搞一个栈