游 戏

【问题描述】 话说前年Alice和Bob相聚在一起玩游戏后，彼此都很忙，因此很少见面。今年由于为了NOIP2020又再次相聚，

他们俩还是想比比谁能够收集到最多的石子数量。Alice将石子分成了$N$堆（编号1..N），并且规定了它们的选取顺序，

刚好形成一颗有向树。在游戏过程中，两人从根节点开始，轮流取走石子，当一个人取走节点$i$的石子后，

另一个人只能从节点$i$的儿子节点中选取一个。当取到某个叶子时游戏结束，然后两人会比较自己得到的石子数量。

已知两人采用的策略不一样，Alice考虑在让Bob取得尽可能少的前提下，自己取的最多；而Bob想得是在自己尽可能取得多的前提下，

让Alice取得最少。在两人都采取最优策略的情况下，请你计算出游戏结束时两人的石子数量。

游戏总是Alice先取，保证只存在一组解。

【输入】

第$1$行只有一个正整数$N$，表示石子堆数；

第$2$行包含$N$个整数，第i个数表示第i堆石子的数量$num[i]$；

第$3..N+1$行，每行两个正整数$u$和$v$，表示节点$u$为节点$v$的父亲；

【输出】

输出文件仅一行为两个整数，分别表示Alice取到的石子数和Bob取到的石子数。

【样例输入】

6

4 16 16 5 3 1

1 2

2 4

1 3

3 5

3 6

【样例输出】

7 16

【样例解释】

首先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

【注意】

保证两人得到的石子数在[0,2^31-1]。

20个测试点