[AGC007E] Shik and Travel

一颗 $n$ 个节点的二叉树，每个节点要么有两个儿子要么没有儿子。边有边权。 你从 $1$ 号节点出发，走到一个叶子节点。然后每一天，你可以从当前点走到另一个叶子。最后回到 $1$ 号节点，要求到过所有叶子并且每条边经过**恰好两次**。 每天的路费是你走过的路径上的边权和，你的公司会为你报销大部分路费，除了你旅行中所用路费最高的，行走路线是**从叶子到叶子**的那一天的路费。 求你自己最少要付多少路费？

[problemUrl]: https://atcoder.jp/contests/agc007/tasks/agc007_e ある国には $ 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 $ 日でなければならない。これらの $ m $ 回の宿泊は、木の葉に相当する都市のすべてで一度ずつ行わなければならない。 - 旅行全体を通じて、この国のすべての道路をそれぞれちょうど二度ずつ通行しなければならない。 - 旅行中に発生する道路の通行料のうち、社員自身が負担しなければならない金額は、発生する通行料の合計が最大であるような日（ただし旅行初日および最終日を除く）に発生する通行料の合計である。残りの金額は会社の負担となる。 シックはこの会社の従業員です。道路通行料補助制度のもとで行う今度の旅行では、発生する通行料のうち自分自身で支払わなければならない金額を最小にすることだけを考えています。そのような旅程を組む手伝いをしてあげてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ v_1 $ $ a_2 $ $ v_2 $ $ . $ $ . $ $ a_{N-1} $ $ v_{N-1} $

道路通行料補助制度のもとで旅行を行うとき、発生する通行料のうち自分自身で負担しなければならない金額の最小値を出力せよ。

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

4

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

6

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

15

3
1 0
1 0

0

### 制約 - $ 2\ <\ N\ <\ 131,072 $ - すべての $ i $ に対し、$ 1\ \leq\ a_i\ \leq\ i $ - $ 0\ \leq\ v_i\ \leq\ 131,072 $ - $ v_i $ は整数である。 - 与えられる木は全二分木である。 ### Sample Explanation 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 $ 回通ってしまい、制度の対象外となってしまいます。下図にこれらの訪問順序に対応する旅行の経路を示します。 !\[04b39e0341af562ba20ba2d49c6f2b69.jpg\](https://atcoder.jp/img/agc007/04b39e0341af562ba20ba2d49c6f2b69.jpg) 制度の対象となるような都市の訪問順序すべてにおいて、対応する旅程では $ 3 $ 日目に $ 4 $ 本の道路を通行して合計で $ 4 $ の通行料が発生し、発生する通行料の合計が最大であるような日はこの日となります。 ### Sample Explanation 2 下図に負担金額が最小となるような旅行の経路をひとつ示します。 !\[92271892911b34032766803fa9c9e159.jpg\](https://atcoder.jp/img/agc007/92271892911b34032766803fa9c9e159.jpg) 負担金額を算出する際に、旅行初日および最終日に発生する通行料は考えないことに注意してください。