E - 水路の整備 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

N 個の集落からなる地域があります。この地域の道路網は木構造になっており、集落 1 が根（中心地）です。各集落 i（2 \leq i \leq N）には親集落 P_i があり、集落 i と集落 P_i は道路で直接結ばれています。道路は全部で N - 1 本あります。

それぞれの道路に沿って水路を 1 本ずつ整備することになりました。各水路の工事には基本工事コスト 1 がかかります。さらに、各水路の工事は、その水路に対応する道路が結ぶ 2 つの集落のうちちょうど一方を担当集落として選び、その集落が工事を請け負います。すなわち、集落 i と集落 P_i を結ぶ道路の水路工事について、集落 P_i が担当するか集落 i が担当するかのいずれかを選びます。すべての水路は必ずいずれかの集落に割り当てなければなりません。

ここで、各集落 i が担当しうる水路は、集落 i を端点とする道路に対応する水路のみです。具体的には、集落 i が根でなければ「集落 i と親 P_i を結ぶ辺」の水路、および「集落 i と各子集落を結ぶ辺」の水路が対象です。集落 1（根）には親がないため、子集落との辺の水路のみが対象です。

各集落 i（1 \leq i \leq N）には工事許容量 C_i と追加コスト係数 W_i が定められています。集落 i が担当することになった水路工事の本数を m_i とします。m_i が C_i 以下であれば追加コストは発生しませんが、m_i が C_i を超えた場合、超過 1 本ごとに W_i の追加コストが発生します。すなわち、集落 i で発生する追加コストは W_i \times \max(0,\, m_i - C_i) です。

総コストは、すべての水路の基本工事コストの合計（常に N - 1）と、すべての集落で発生する追加コストの和です：

\displaystyle (N - 1) + \sum_{i=1}^{N} W_i \times \max(0,\, m_i - C_i)

すべての水路について担当する集落を最適に決めたとき、総コストの最小値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq i - 1（2 \leq i \leq N）
  • 0 \leq C_i \leq N（1 \leq i \leq N）
  • 1 \leq W_i \leq 10^9（1 \leq i \leq N）
  • 入力はすべて整数である。

入力

N
P_2 P_3 \ldots P_N
C_1 W_1
C_2 W_2
\vdots
C_N W_N
  • 1 行目には、集落の数 N が与えられる。
  • 2 行目には、集落 2, 3, \ldots, N の親集落を表す P_2, P_3, \ldots, P_N がスペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、集落 i の工事許容量 C_i と追加コスト係数 W_i がスペース区切りで与えられる。

出力

総コストの最小値を 1 行で出力せよ。

入力例 1

4
1 1 2
1 3
0 5
2 2
0 4

出力例 1

7

入力例 2

5
1 1 1 1
0 10
1 1
0 7
2 3
0 2

出力例 2

13

入力例 3

12
1 1 2 2 3 3 4 4 6 6 10
1 8
2 3
0 10
1 6
0 2
2 5
1 9
0 4
3 1
1 7
0 3
2 6

出力例 3

13

入力例 4

30
1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 10 10 11 12 13 14 15 16 17 18 20 24
1 100
3 5
0 20
2 7
1 12
3 4
0 50
1 9
2 6
0 30
4 2
1 15
0 11
2 8
1 25
0 3
2 18
1 10
3 1
0 40
1 13
2 5
0 17
1 22
3 6
0 14
2 9
1 16
0 19
4 2

出力例 4

115

入力例 5

2
1
0 1000000000
2 1

出力例 5

1

Score : 433 pts

Problem Statement

There is a region consisting of N settlements. The road network of this region forms a tree structure, with settlement 1 as the root (central hub). Each settlement i (2 \leq i \leq N) has a parent settlement P_i, and settlement i and settlement P_i are directly connected by a road. There are N - 1 roads in total.

It has been decided to develop one waterway along each road. The construction of each waterway incurs a basic construction cost of 1. Furthermore, for each waterway construction, exactly one of the two settlements connected by the corresponding road must be chosen as the responsible settlement, and that settlement undertakes the construction. That is, for the waterway construction along the road connecting settlement i and settlement P_i, either settlement P_i or settlement i is chosen to be responsible. Every waterway must be assigned to one of the settlements.

Here, the waterways that each settlement i can be responsible for are only those corresponding to roads that have settlement i as an endpoint. Specifically, if settlement i is not the root, the eligible waterways are those for "the edge connecting settlement i and its parent P_i" and "the edges connecting settlement i and each of its child settlements." For settlement 1 (the root), which has no parent, only the waterways for edges to its child settlements are eligible.

For each settlement i (1 \leq i \leq N), a construction capacity C_i and an additional cost coefficient W_i are defined. Let m_i be the number of waterway constructions assigned to settlement i. If m_i is at most C_i, no additional cost is incurred. However, if m_i exceeds C_i, an additional cost of W_i is incurred for each excess waterway. That is, the additional cost incurred at settlement i is W_i \times \max(0,\, m_i - C_i).

The total cost is the sum of the basic construction costs of all waterways (always N - 1) plus the sum of additional costs incurred at all settlements:

\displaystyle (N - 1) + \sum_{i=1}^{N} W_i \times \max(0,\, m_i - C_i)

Determine the minimum total cost when the responsible settlement for each waterway is chosen optimally.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
  • 0 \leq C_i \leq N (1 \leq i \leq N)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N
P_2 P_3 \ldots P_N
C_1 W_1
C_2 W_2
\vdots
C_N W_N
  • The first line gives the number of settlements N.
  • The second line gives P_2, P_3, \ldots, P_N, representing the parent settlements of settlements 2, 3, \ldots, N, separated by spaces.
  • In the following N lines, the i-th line (1 \leq i \leq N) gives the construction capacity C_i and additional cost coefficient W_i of settlement i, separated by a space.

Output

Output the minimum total cost in a single line.

Sample Input 1

4
1 1 2
1 3
0 5
2 2
0 4

Sample Output 1

7

Sample Input 2

5
1 1 1 1
0 10
1 1
0 7
2 3
0 2

Sample Output 2

13

Sample Input 3

12
1 1 2 2 3 3 4 4 6 6 10
1 8
2 3
0 10
1 6
0 2
2 5
1 9
0 4
3 1
1 7
0 3
2 6

Sample Output 3

13

Sample Input 4

30
1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 10 10 11 12 13 14 15 16 17 18 20 24
1 100
3 5
0 20
2 7
1 12
3 4
0 50
1 9
2 6
0 30
4 2
1 15
0 11
2 8
1 25
0 3
2 18
1 10
3 1
0 40
1 13
2 5
0 17
1 22
3 6
0 14
2 9
1 16
0 19
4 2

Sample Output 4

115

Sample Input 5

2
1
0 1000000000
2 1

Sample Output 5

1