问题描述

样例输入 1

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

样例输出 1

4

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

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

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

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

约束条件

• $2 < N < 131,072$
• 对于所有 $i$，$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

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

对于所有有效的顺序，第 $3$ 天的总过路费最大为 $4$，经过了 $4$ 条道路。

样例解释 2

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

样例解释 3

样例解释 4