C - Company Positions and Salaries Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、ある会社の人事部で働いています。この会社には N 人の社員がおり、組織は木構造になっています。

社員 1 が社長（組織のトップ）であり、各社員 i （ 2 \leq i \leq N ）の直属の上司は社員 P_i です。

高橋君は、各社員に「給与ランク」と呼ばれる正の整数値を割り当てる必要があります。ただし、以下の条件を満たさなければなりません。

  • 社長（社員 1 ）の給与ランクは 1 である。
  • 各社員の給与ランクは、その直属の上司の給与ランク以上である。
  • 各社員 i には「上限ランク」 U_i が設定されており、社員 i の給与ランクは U_i 以下でなければならない。

高橋君は、すべての社員の給与ランクの合計を最大化したいと考えています。

条件を満たす給与ランクの割り当てが存在する場合は、給与ランクの合計の最大値を求めてください。条件を満たす割り当てが存在しない場合は -1 を出力してください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

N
U_1
P_2 U_2
P_3 U_3
:
P_N U_N
  • 1 行目には、社員の数を表す N が与えられる。
  • 2 行目には、社員 1 （社長）の上限ランク U_1 が与えられる。
  • 3 行目から N + 1 行目には、社員 i （ 2 \leq i \leq N ）の直属の上司 P_i と上限ランク U_i がスペース区切りで与えられる。

出力

条件を満たす給与ランクの割り当てが存在する場合は、すべての社員の給与ランクの合計の最大値を 1 行で出力してください。存在しない場合は -1 を出力してください。

入力例 1

5
3
1 4
1 2
2 5
2 4

出力例 1

16

入力例 2

4
5
1 3
1 0
2 4

出力例 2

-1

入力例 3

15
10
1 6
1 12
2 8
2 3
3 15
3 7
4 9
4 5
5 4
6 20
6 11
7 13
7 2
10 6

出力例 3

97

入力例 4

30
100
1 50
1 80
2 45
2 60
3 90
3 30
4 55
4 25
5 70
5 65
6 95
6 40
7 35
7 85
8 20
8 75
9 15
9 1000000000
10 10
10 68
11 72
11 58
12 99
12 33
13 44
13 88
14 22
14 77
15 66

出力例 4

1000001124

入力例 5

1
1

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi works in the HR department of a company. The company has N employees, and the organization has a tree structure.

Employee 1 is the president (the top of the organization), and the direct supervisor of each employee i (2 \leq i \leq N) is employee P_i.

Takahashi needs to assign a positive integer value called a "salary rank" to each employee. However, the following conditions must be satisfied:

  • The salary rank of the president (employee 1) is 1.
  • The salary rank of each employee is greater than or equal to the salary rank of their direct supervisor.
  • Each employee i has an "upper rank limit" U_i, and the salary rank of employee i must be at most U_i.

Takahashi wants to maximize the total salary rank of all employees.

If a valid assignment of salary ranks satisfying the conditions exists, find the maximum total of all salary ranks. If no valid assignment exists, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq U_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_i < i (2 \leq i \leq N)
  • All inputs are integers.

Input

The input is given from standard input in the following format:

N
U_1
P_2 U_2
P_3 U_3
:
P_N U_N
  • The first line contains N, representing the number of employees.
  • The second line contains U_1, the upper rank limit of employee 1 (the president).
  • From the third line to the (N+1)-th line, the direct supervisor P_i and the upper rank limit U_i of employee i (2 \leq i \leq N) are given, separated by a space.

Output

If a valid assignment of salary ranks satisfying the conditions exists, output the maximum total of all employees' salary ranks in one line. If no valid assignment exists, output -1.

Sample Input 1

5
3
1 4
1 2
2 5
2 4

Sample Output 1

16

Sample Input 2

4
5
1 3
1 0
2 4

Sample Output 2

-1

Sample Input 3

15
10
1 6
1 12
2 8
2 3
3 15
3 7
4 9
4 5
5 4
6 20
6 11
7 13
7 2
10 6

Sample Output 3

97

Sample Input 4

30
100
1 50
1 80
2 45
2 60
3 90
3 30
4 55
4 25
5 70
5 65
6 95
6 40
7 35
7 85
8 20
8 75
9 15
9 1000000000
10 10
10 68
11 72
11 58
12 99
12 33
13 44
13 88
14 22
14 77
15 66

Sample Output 4

1000001124

Sample Input 5

1
1

Sample Output 5

1