题目背景

形禁势格，利从近取，害以远隔。上火下泽。

题目描述

有 $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$ 个国家的战斗力之和。

6
100 10 42 33 56 1000 
0 0
0 0
0 6
0 0
3 2
4 1

166

如图，即 $3,6,4,1$ 都比 $5$ 离得近，$2$ 比 $5$ 离得远。$6,4,1$ 比 $3$ 离得远。$4$ 比 $6$ 离得近，$1$ 比 $6$ 离得远。

最远的三个点为 $1,5,2$，战斗力之和为 $100+56+10=166$

3
1000 33 124
0 2
0 3
0 0

124

三个节点从近到远依次是 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 分）：没有特殊限制。