题面翻译

一颗 $n$ 个节点的二叉树，每个节点要么有两个儿子要么没有儿子。边有边权。

你从 $1$ 号节点出发，走到一个叶子节点。然后每一天，你可以从当前点走到另一个叶子。最后回到 $1$ 号节点，要求到过所有叶子并且每条边经过恰好两次。

每天的路费是你走过的路径上的边权和，你的公司会为你报销大部分路费，除了你旅行中所用路费最高的，行走路线是从叶子到叶子的那一天的路费。

求你自己最少要付多少路费？

样例 #1

样例输入 #1

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

样例输出 #1

4

样例 #2

样例输入 #2

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

样例输出 #2

6

样例 #3

样例输入 #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

样例输入 #4

3
1 0
1 0

样例输出 #4

0

提示

制約

• $2\ <\ N\ <\ 131,072$
• すべての $i$ に対し、$1\ \leq\ a_i\ \leq\ i$
• $0\ \leq\ v_i\ \leq\ 131,072$
• $v_i$ は整数である。
• 与えられる木は全二分木である。