AT_agc007_e.[AGC007E] Shik and Travel

在某个国家有 $N$ 个城市，这些城市通过 $N-1$ 条道路相连。道路是双向通行的。为了方便，城市编号为 $1$ 到 $N$，道路编号为 $1$ 到 $N-1$。用图论的术语来说，对于任意两个城市，恰好存在一条连接它们的简单路径。也就是说，由城市和道路构成的图是一棵树。此外，如果将 $1$ 号城市作为这棵树的根，这棵树是一棵完全二叉树（完全二叉树指的是，除叶子节点外的每个节点恰好有两个子节点的有根树）。第 $i$ 条道路连接 $i+1$ 号城市和 $a_i$ 号城市，每次通过该道路需要支付 $v_i$ 的通行费（如果 $v_i=0$，则不需要支付通行费）。

在 $1$ 号城市，有一家以鼓励员工旅游而闻名的公司。该公司有一项道路通行费补助制度，在员工旅行期间产生的大部分道路通行费由公司承担。要使旅行符合该制度的适用条件，需要满足一些限制条件，在这些条件范围内可以自由安排行程。具体如下：

• 要适用该制度，旅行的出发点和终点都必须是 $1$ 号城市。此外，将该国的城市和道路视为以 $1$ 号城市为根的有根树时，若该树有 $m$ 个叶子节点，则旅行日程必须为 $m$ 晚 $m+1$ 天。必须在所有叶子节点对应的城市各住宿一次。
• 在整个旅行过程中，必须恰好每条道路都经过两次。
• 在旅行期间产生的道路通行费中，员工本人需要承担的金额为除去旅行第一天和最后一天外，某一天产生的通行费总额的最大值。剩余部分由公司承担。

Shick 是该公司的员工。在享受道路通行费补助制度的这次旅行中，他只关心如何使自己需要支付的通行费金额最小。请帮他安排这样的旅行路线。

输入通过标准输入按以下格式给出。

$N$ $a_1$ $v_1$ $a_2$ $v_2$ $\cdots$ $a_{N-1}$ $v_{N-1}$

输出在道路通行费补助制度下进行旅行时，员工本人需要承担的通行费的最小值。

限制条件

• $2 < N < 131072$
• 对于所有 $i$，$1 \leq a_i \leq i$
• $0 \leq v_i \leq 131072$
• $v_i$ 为整数
• 给定的树为完全二叉树

样例解释 1

将城市和道路视为以 $1$ 号城市为根的有根树时，该树有 $4$ 个叶子节点（对应 $4, 5, 6, 7$ 号城市），因此旅行日程为 $4$ 晚 $5$ 天。对于这 $4$ 个城市的住宿顺序有 $4! = 24$ 种，但其中部分顺序不符合制度要求。例如，按 $(4,5,6,7)$ 或 $(6,7,5,4)$ 的顺序访问城市时符合制度要求，但按 $(5,6,7,4)$ 的顺序访问时，会在行程中第 $1$ 号城市和第 $2$ 号城市之间的道路上经过 $4$ 次，不符合制度要求。下图展示了这些访问顺序对应的旅行路径。 在所有符合制度要求的城市访问顺序中，对应的行程在第 $3$ 天会经过 $4$ 条道路，通行费总额为 $4$，这一天的通行费总额为最大值。

样例解释 2

下图展示了一种使员工负担金额最小的旅行路径。 需要注意的是，计算员工负担金额时，不考虑旅行第一天和最后一天产生的通行费。

由 ChatGPT 4.1 翻译