E - Shik and Travel Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

Score : 1400 points

Problem Statement

In the country there are N cities numbered 1 through N, which are connected by N-1 bidirectional roads. In terms of graph theory, there is a unique simple path connecting every pair of cities. That is, the N cities form a tree. Besides, if we view city 1 as the root of this tree, the tree will be a full binary tree (a tree is a full binary tree if and only if every non-leaf vertex in the tree has exactly two children). Roads are numbered 1 through N-1. The i-th road connects city i+1 and city a_i. When you pass through road i, the toll you should pay is v_i (if v_i is 0, it indicates the road does not require a toll).

A company in city 1 will give each employee a family travel and cover a large part of the tolls incurred. Each employee can design the travel by themselves. That is, which cities he/she wants to visit in each day and which city to stay at each night. However, there are some constraints. More details are as follows:

  • The travel must start and end at city 1. If there are m leaves in the tree formed by the cities, then the number of days in the travel must be m+1. At the end of each day, except for the last day, the employee must stay at some hotel in a leaf city. During the whole travel, the employee must stay at all leaf cities exactly once.

  • During the whole travel, all roads of the country must be passed through exactly twice.

  • The amount that the employee must pay for tolls by him/herself is the maximum total toll incurred in a single day during the travel, except the first day and the last day. The remaining tolls will be covered by the company.

Shik, as an employee of this company, has only one hope for his travel. He hopes that the amount he must pay for tolls by himself will be as small as possible. Please help Shik to design the travel which satisfies his hope.

Constraints

  • 2 < N < 131,072
  • 1 \leq a_i \leq i for all i
  • 0 \leq v_i \leq 131,072
  • v_i is an integer
  • The given tree is a full binary tree

Input

The input is given from Standard Input in the following format:

N
a_1 v_1
a_2 v_2
:
a_{N-1} v_{N-1}

Output

Print an integer denoting the minimum amount Shik must pay by himself for tolls incurred during the travel.

Sample Input 1

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

Sample Output 1

4

There are 4 leaves in the tree formed by the cities (cities 4, 5, 6, and 7), so the travel must be 5 days long. There are 4! = 24 possible arrangements of the leaf cities to stay during the travel, but some of them are invalid. For example, (4,5,6,7) and (6,7,5,4) are valid orders, but (5,6,7,4) is invalid because the route passes 4 times through the road connecting city 1 and city 2. The figure below shows the routes of the travel for these arrangements.

04b39e0341af562ba20ba2d49c6f2b69.jpg

For all valid orders, day 3 is the day with the maximum total incurred toll of 4, passing through 4 roads.

Sample Input 2

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

Sample Output 2

6

The following figure shows the route of the travel for one possible arrangement of the stayed cities for the solution. Note that the tolls incurred in the first day and the last day are always covered by the company.

92271892911b34032766803fa9c9e159.jpg

Sample Input 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

Sample Output 3

15

Sample Input 4

3
1 0
1 0

Sample Output 4

0

配点 : 1400 点

問題文

ある国には 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 回の宿泊は、木の葉に相当する都市のすべてで一度ずつ行わなければならない。

  • 旅行全体を通じて、この国のすべての道路をそれぞれちょうど二度ずつ通行しなければならない。

  • 旅行中に発生する道路の通行料のうち、社員自身が負担しなければならない金額は、発生する通行料の合計が最大であるような日（ただし旅行初日および最終日を除く）に発生する通行料の合計である。残りの金額は会社の負担となる。

シックはこの会社の従業員です。道路通行料補助制度のもとで行う今度の旅行では、発生する通行料のうち自分自身で支払わなければならない金額を最小にすることだけを考えています。そのような旅程を組む手伝いをしてあげてください。

制約

  • 2 < N < 131,072
  • すべての i に対し、1 \leq a_i \leq 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}

出力

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

入力例 1

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

出力例 1

4

都市と道路を 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

制度の対象となるような都市の訪問順序すべてにおいて、対応する旅程では 3 日目に 4 本の道路を通行して合計で 4 の通行料が発生し、発生する通行料の合計が最大であるような日はこの日となります。

入力例 2

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

出力例 2

6

下図に負担金額が最小となるような旅行の経路をひとつ示します。

92271892911b34032766803fa9c9e159.jpg

負担金額を算出する際に、旅行初日および最終日に発生する通行料は考えないことに注意してください。

入力例 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

3
1 0
1 0

出力例 4

0