题目描述

Alice和Bob想比比谁能够收集到最多的石子数量。 Alice将石子分成了$n$堆（编号$1…n$），并且规定了它们的选取顺序，刚好形成一颗有向树。在游戏过程中，两人从根节点开始，轮流取走石子（一次取一堆），当一个人取走结点$i$的石子后，另一个人只能从结点$i$的儿子节点中选取一个。当取到叶子结点时游戏结束。 然后两人会比较自己得到的石子数量。已知两人采用的策略不同，Alice希望在让Bob取得尽可能少的前提下，自己取得最多；而Bob希望在自己取得尽可能多的前提下，让Alice取得最少。在两人都采取最优策略的情况下，请你计算出游戏结束时两人的石子数量。 游戏总是Alice先取，保证只存在一组解。

输入

第一行包含一个正整数$n$，表示石子堆数。 第二行包含$n$个整数，其中第$i$个数表示第$i$堆石子的数量$num[i]$。 接下来$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$，Bob均能得到$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^4$。 对于100%的数据，$1≤n≤10^5，1≤num[i]≤10^4$。保证两人得到的石子总数在$[0,2^{31})$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。