#C. 远交近攻

    传统题 文件IO:yuan 1000ms 256MiB

远交近攻

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

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

题目描述

nn 个国家,编号从 1n1\sim n。第 ii 个国家的战斗力为 aia_i

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

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

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

输入格式

第一行一个整数 nn

第二行 nn 个整数,即 a1ana_1\sim a_n

接下来 nn 行,第 ii 行为节点 ii 的左子节点和右子节点 li,ril_i,r_i(如果不存在,则值为 00)。

输出格式

一个整数,即最远的 n2\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,13,6,4,1 都比 55 离得近,2255 离得远。6,4,16,4,133 离得远。4466 离得近,1166 离得远。

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

3
1000 33 124
0 2
0 3
0 0
124

三个节点从近到远依次是 1,2,3,最远的 32=1\lfloor\frac{3}{2}\rfloor=1 个点是 33 号点,战斗力为 124124

数据规模与约定

对于 100%100\% 的数据,1n1000001 \le n \le 1000001ai10001\le a_i\le 1000

  • 子任务 1(10 分):保证所有 aia_i 都相等。
  • 子任务 2(20 分):保证 li=0l_i=0
  • 子任务 3(30 分):保证 n=100n=100
  • 子任务 4(40 分):没有特殊限制。

挖土机 CSP-J 模拟赛 ~ 第十二场

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-10-7 4:00
结束于
2024-10-9 4:00
持续时间
3.5 小时
主持人
参赛人数
79