分数: 1400 点
问题陈述
在国内有 N 城市编号 1 通过 N,通过以下方式连接 N-1 双向道路。从图论的角度来看,每对城市之间都有一条独特的简单路径连接。也就是说, N 城市形成一棵树。此外,如果我们查看城市 1 作为这棵树的根,这棵树将是一个满二叉树(当且仅当树中的每个非叶顶点都有两个子节点时,树才是满二叉树)。道路已编号 1 通过 N-1.The i第条路连接城市 i+1 和城市 a_i。当你经过马路时 i,您应该支付的通行费是 v_i (如果 v_i is 0,表示该路段不需要收费)。
市某公司 1 将为每位员工提供一次家庭旅行,并承担大部分路费。每个员工都可以自己设计行程。即他/她每天想去哪些城市,每天晚上要住在哪个城市。然而,也存在一些限制。更多详情如下:
-
行程必须在城市开始和结束 1。如果有 m 城市形成的树中存在叶子,则旅行的天数必须为 m+1。每天结束时,除了最后一天外,员工必须住在叶子城市的某个酒店。整个行程中,员工必须在所有叶子城市停留一次。
-
整个旅行过程中,必须经过全国所有道路恰好两次。
-
员工须自行缴纳的路费金额为行程期间单日最高总路费总额(第一天和最后一天除外)。剩余的通行费将由公司承担。
Shik作为这家公司的员工,对于旅行只有一个希望。他希望自己必须支付的过路费尽可能少。请帮助Shik设计一次满足他愿望的旅行。
约束
- 2 < N < 131,072
- 1 \leq a_i \leq i 对于所有人 i
- 0 \leq v_i \leq 131,072
- v_i 是一个整数
- 给定的树是满二叉树
输入
输入由标准输入按以下格式给出:
N
a_1 v_1
a_2 v_2
:
a_{N-1} v_{N-1}
输出
打印一个整数,表示 Shik 必须自行支付旅行期间产生的过路费的最低金额。
样本输入 1
7 1 1 1 1 2 1 2 1 3 1 3 1
示例输出 1
4
有 4 城市组成的树中的叶子(城市 4, 5, 6,和 7),所以行程必须是 5 天长了。有 4! = 24 叶子城市旅行期间可能有住宿安排,但部分无效。例如, (4,5,6,7) 和 (6,7,5,4) 是有效订单,但是 (5,6,7,4) 无效,因为该路线经过 4 次通公路连接城市 1 和城市 2。下图显示了这些安排的行进路线。
对于所有有效订单,日 3 是总通行费最高的日期 4,经过 4 道路。
示例输入 2
9 1 2 1 2 3 2 3 2 5 2 5 2 7 2 7 2
示例输出 2
6
下图显示了该解决方案的一种可能的停留城市安排的出行路线。请注意,第一天和最后一天产生的通行费始终由公司承担。
示例输入 3
15 1 2 1 5 3 3 4 3 4 3 6 5 5 4 5 3 6 3 3 2 11 5 11 3 13 2 13 1
示例输出 3
15
示例输入 4
3 1 0 1 0
示例输出 4
0