C - 避難訓練の混雑度 解説 /

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

配点 : 366 点

問題文

高橋君は、N 個の広場からなる公園の避難訓練を管理しています。広場は 1 から N まで番号付けされており、N-1 本の道によって結ばれ、広場 1 を根とする木構造をなしています。各広場 i（2 \leq i \leq N）には親となる広場 P_i が定まっており、広場 i と広場 P_i は道で直接結ばれています。

各広場 i には混雑係数 A_i が設定されています。また、各広場 i には B_i 人がいます。

避難訓練では、各広場 i（2 \leq i \leq N）にいる B_i 人が、避難場所である広場 1 へ向かいます。各人は、広場 i から広場 1 への木上の一意な単純パスに沿って移動し、始点 i と終点 1 を含むパス上のすべての広場を通過します。

広場 1 にいる B_1 人はすでに避難場所にいるため移動せず、どの広場も通過しないものとします。

避難訓練の混雑度を、すべての移動する人について、その人が通過するすべての広場の混雑係数の総和として定義します。すなわち、

\text{混雑度} = \sum_{i=2}^{N} B_i \sum_{j \in \mathrm{path}(i,1)} A_j

です。ここで \mathrm{path}(i,1) は広場 i から広場 1 への単純パス上の広場の集合（両端を含む）を表します。

混雑度を求めてください。

制約

  • 1 \leq N \leq 3 \times 10^5
  • 0 \leq A_i \leq 10^4 (1 \leq i \leq N)
  • 1 \leq P_i < i (2 \leq i \leq N)
  • 0 \leq B_i \leq 10^4 (1 \leq i \leq N)
  • 入力はすべて整数である。
  • 答えは 2^{63}-1 以下であることが保証される。

入力

N
A_1 A_2 \dots A_N
P_2 P_3 \dots P_N
B_1 B_2 \dots B_N
  • 1 行目には、広場の数を表す整数 N が与えられる。
  • 2 行目には、各広場の混雑係数を表す N 個の整数 A_1, A_2, \dots, A_N がスペース区切りで与えられる。
  • 3 行目には、木構造における各広場の親を表す N-1 個の整数 P_2, P_3, \dots, P_N がスペース区切りで与えられる。広場 i（2 \leq i \leq N）の親は広場 P_i である。
  • 4 行目には、各広場にいる人数を表す N 個の整数 B_1, B_2, \dots, B_N がスペース区切りで与えられる。

出力

混雑度を 1 行に出力せよ。

入力例 1

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

出力例 1

33

入力例 2

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

出力例 2

68

入力例 3

8
5 3 6 1 4 0 2 8
1 1 2 2 3 3 6
9 2 3 4 0 5 1 6

出力例 3

267

入力例 4

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

出力例 4

811

入力例 5

1
10000

10000

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is managing an evacuation drill in a park consisting of N plazas. The plazas are numbered from 1 to N and connected by N-1 paths, forming a tree structure rooted at plaza 1. For each plaza i (2 \leq i \leq N), there is a designated parent plaza P_i, and plaza i and plaza P_i are directly connected by a path.

Each plaza i has a congestion coefficient A_i. Also, there are B_i people at each plaza i.

During the evacuation drill, the B_i people at each plaza i (2 \leq i \leq N) head toward plaza 1, which is the evacuation site. Each person moves along the unique simple path on the tree from plaza i to plaza 1, passing through all plazas on the path including the starting point i and the endpoint 1.

The B_1 people at plaza 1 are already at the evacuation site and do not move, so they do not pass through any plaza.

The congestion of the evacuation drill is defined as the sum, over all moving people, of the total congestion coefficients of all plazas that person passes through. That is,

\text{Congestion} = \sum_{i=2}^{N} B_i \sum_{j \in \mathrm{path}(i,1)} A_j

Here, \mathrm{path}(i,1) denotes the set of plazas on the simple path from plaza i to plaza 1 (including both endpoints).

Find the congestion.

Constraints

  • 1 \leq N \leq 3 \times 10^5
  • 0 \leq A_i \leq 10^4 (1 \leq i \leq N)
  • 1 \leq P_i < i (2 \leq i \leq N)
  • 0 \leq B_i \leq 10^4 (1 \leq i \leq N)
  • All input values are integers.
  • It is guaranteed that the answer is at most 2^{63}-1.

Input

N
A_1 A_2 \dots A_N
P_2 P_3 \dots P_N
B_1 B_2 \dots B_N
  • The first line contains an integer N, the number of plazas.
  • The second line contains N integers A_1, A_2, \dots, A_N separated by spaces, representing the congestion coefficient of each plaza.
  • The third line contains N-1 integers P_2, P_3, \dots, P_N separated by spaces, representing the parent of each plaza in the tree structure. The parent of plaza i (2 \leq i \leq N) is plaza P_i.
  • The fourth line contains N integers B_1, B_2, \dots, B_N separated by spaces, representing the number of people at each plaza.

Output

Print the congestion on a single line.

Sample Input 1

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

Sample Output 1

33

Sample Input 2

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

Sample Output 2

68

Sample Input 3

8
5 3 6 1 4 0 2 8
1 1 2 2 3 3 6
9 2 3 4 0 5 1 6

Sample Output 3

267

Sample Input 4

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

Sample Output 4

811

Sample Input 5

1
10000

10000

Sample Output 5

0