← 返回题目列表

AtCoder · agc007_e

E. 希克和旅行

中文机器翻译题面 查看原题

分数: 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。下图显示了这些安排的行进路线。

04b39e0341af562ba20ba2d49c6f2b69.jpg

对于所有有效订单,日 3 是总通行费最高的日期 4,经过 4 道路。


示例输入 2

9
1 2
1 2
3 2
3 2
5 2
5 2
7 2
7 2

示例输出 2

6

下图显示了该解决方案的一种可能的停留城市安排的出行路线。请注意,第一天和最后一天产生的通行费始终由公司承担。

92271892911b34032766803fa9c9e159.jpg

示例输入 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