#agc007e. [agc007_e]Shik and Travel

[agc007_e]Shik and Travel

问题描述

样例输入 1

7
1 1
1 1
2 1
2 1
3 1
3 1

样例输出 1

在这个国家中,有 NN 个城市,编号从 11NN,它们之间通过 N1N-1 条双向道路相连。从图论的角度看,连接每对城市的路径都是唯一的。也就是说,NN 个城市形成了一棵树。此外,如果我们将城市 11 视为这棵树的根节点,那么这棵树将是一棵满二叉树(当且仅当树中的非叶节点都恰有两个子节点时,树称为满二叉树)。道路的编号从 11N1N-1。第 ii 条道路连接城市 i+1i+1 和城市 aia_i。当你经过第 ii 条道路时,你需要支付的过路费是 viv_i(如果 viv_i00,则表示该道路不需要过路费)。

该公司在城市 11 给每位员工提供一个家庭旅行,并支付了大部分的过路费。每位员工可以自己设计旅行计划。也就是说,在每天的旅行中,他/她可以决定自己想要参观的城市以及每天晚上在哪个城市住宿。然而,有一些限制。更多细节如下:

  • 旅行必须从城市 11 开始并在城市 11 结束。如果树形成的叶子节点数为 mm,那么旅行的天数必须是 m+1m+1。除了最后一天外,在每天结束时,员工必须在一个叶子城市的某个酒店住宿。在整个旅行过程中,员工必须恰好一次地住在所有叶子城市。
  • 在整个旅行过程中,必须恰好经过全国所有道路两次。
  • 员工自己需要支付的过路费金额是旅行中一天的最大总过路费(不包括第一天和最后一天)。剩余的过路费将由公司支付。

Shik 是这家公司的一名员工,对于他的旅行,他只希望他自己需要支付的过路费最少。请帮助 Shik 设计满足他期望的旅行计划。

约束条件

  • 2<N<131,0722 < N < 131,072
  • 对于所有 ii1leqaileqi1 \\leq a_i \\leq i
  • 对于所有 ii0leqvileq131,0720 \\leq v_i \\leq 131,072
  • viv_i 是整数
  • 给定的树是满二叉树

输入

输入以以下格式从标准输入给出:

NN a1a_1 v1v_1 a2a_2 v2v_2 :: aN1a_{N-1} vN1v_{N-1}

输出

输出一个整数,表示 Shik 自己在旅行过程中需要支付的最少过路费金额。

样例解释 1

树形成的叶子节点有 44 个(城市 44556677),所以旅行的天数必须是 55。有 4!=244! = 24 种可能的叶子城市住宿安排方式,但其中一些是无效的。例如,(4,5,6,7)(4,5,6,7)(6,7,5,4)(6,7,5,4) 是有效的顺序,但 (5,6,7,4)(5,6,7,4) 是无效的,因为该路线通过连接城市 11 和城市 22 的道路 44 次。下图显示了这些安排方式的旅行路线。

04b39e0341af562ba20ba2d49c6f2b69.jpg

对于所有有效的顺序,第 33 天的总过路费最大为 44,经过了 44 条道路。

样例解释 2

下图显示了一种解决方案中待留城市的可能安排方式的旅行路线。请注意,第一天和最后一天的过路费始终由公司支付。

92271892911b34032766803fa9c9e159.jpg

样例解释 3

样例解释 4