3940: 远交近攻(挖土机 CSP-J 模拟赛 ~ 第十二场)

有 $�$ 个国家，编号从 $1\sim �$。第 $�$ 个国家的战斗力为 ${�}_{�}$。

Kitten 是猫猫国的国王（不在这 $�$ 个国家内），为了分析这 $�$ 个国家到猫猫国的距离（保证每个国家到猫猫国的距离都不一样），33DAI 帮她构建了一棵二叉树。

二叉树中有 $�$ 个节点，每个节点都表示对应的那个国家。保证对于二叉树的每个节点 $�$，它左子树中的所有节点都比它离猫猫国更近，它右子树中的所有节点都比它离猫猫国更远。

现在 Kitten 准备攻打最远的 $\lfloor \frac{�}{2}\rfloor$ 个国家，请问这些国家的战斗力之和为多少。

第一行一个整数 $�$。

第二行 $�$ 个整数，即 ${�}_1\sim {�}_{�}$

接下来 $�$ 行，第 $�$ 行为节点 $�$ 的左子节点和右子节点 ${�}_{�},{�}_{�}$（如果不存在，则值为 $0$）。

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

166