题目描述
【题目背景】
形禁势格，利从近取，害以远隔。上火下泽。
有 $n$ 个国家，编号从 $1\sim n$。第 $i$ 个国家的战斗力为 $a_i$。
Kitten 是猫猫国的国王（不在这 $n$ 个国家内），为了分析这 $n$ 个国家到猫猫国的距离（保证每个国家到猫猫国的距离都不一样），33DAI 帮她构建了一棵二叉树。
二叉树中有 $n$ 个节点，每个节点都表示对应的那个国家。保证对于二叉树的每个节点 $u$，它左子树中的所有节点都比它离猫猫国更近，它右子树中的所有节点都比它离猫猫国更远。
现在 Kitten 准备攻打最远的 $\lfloor\frac{n}{2}\rfloor$ 个国家，请问这些国家的战斗力之和为多少。
输入
第一行一个整数 $n$。
第二行 $n$ 个整数，即 $a_1\sim a_n$
接下来 $n$ 行，第 $i$ 行为节点 $i$ 的左子节点和右子节点 $l_i,r_i$（如果不存在，则值为 $0$）。
输出
一个整数，即最远的 $\lfloor\frac{n}{2}\rfloor$ 个国家的战斗力之和。
样例输入输出
输入#1
复制
6
100 10 42 33 56 1000
0 0
0 0
0 6
0 0
3 2
4 1
输入#2
复制
3
1000 33 124
0 2
0 3
0 0
提示
【样例1解释】
如图，即 $3,6,4,1$ 都比 $5$ 离得近，$2$ 比 $5$ 离得远。$6,4,1$ 比 $3$ 离得远。$4$ 比 $6$ 离得近，$1$ 比 $6$ 离得远。
最远的三个点为 $1,5,2$，战斗力之和为 $100+56+10=166$
【样例2解释】
三个节点从近到远依次是 `1,2,3`，最远的 $\lfloor\frac{3}{2}\rfloor=1$ 个点是 $3$ 号点，战斗力为 $124$。
【数据规模与约定】
对于 $100\%$ 的数据，$1 \le n \le 100000$，$1\le a_i\le 1000$。
- 子任务 1（10 分）：保证所有 $a_i$ 都相等。
- 子任务 2（20 分）：保证 $l_i=0$。
- 子任务 3（30 分）：保证 $n=100$
- 子任务 4（40 分）：没有特殊限制。