SUMMAX4


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 103M

Problem type

Cho đồ thị dạng cây gồm N đỉnh, các đỉnh được đánh số từ 1 đến \(N\),mỗi đỉnh \(𝑣\) được gán một số nguyên dương \(𝑎_𝑣\). Gọi \(𝑑𝑖𝑠(𝑥, 𝑦)\) là khoảng cách giữa 2 đỉnh \(𝑥, 𝑦\), khoảng cách được tính bằng số cạnh trên đường đi đơn từ \(𝑥\) đến \(𝑦\). Mỗi khi chọn một đỉnh \(𝑣\) bất kì làm gốc thì ta thu được tổng giá trị của cây là: \(dist(v,1)\)x \(a[1]\)+ \(dist(v,2)\) x \(a[2]\) + … + \(dist(v,n)\) x \(a[n].\)

Hãy tìm giá trị lớn nhất có thể của cây.

Input:

  • Dòng đầu tiên là số \(𝑁\) là số đỉnh của đồ thị.

  • Dòng tiếp theo ghi \(𝑁\) số nguyên dương \(𝑎_1, 𝑎_2, … 𝑎_𝑁\) là các số được gán với \(𝑁\) đỉnh theo thứ tự.

  • Dòng tiếp theo có \(𝑁\) số \(𝑝_1, 𝑝_2, . . 𝑝_𝑁\) thể hiện có đường đi từ đỉnh \(𝑖\) đến \(𝑝_𝑖, 𝑝_𝑖 = 0\) thì đỉnh \(𝑖\) là đỉnh gốc ban đầu, còn lại \(1 ≤ 𝑝_𝑖 ≤ 𝑁\).

Output:

Một số duy nhất là giá trị lớn nhất có thể của cây.

Ràng buộc:

\(𝑁 ≤ 200000, 1 ≤ 𝑎_𝑖 ≤ 200000.\)

Sample Input

14

3 2 1 10 1 3 9 1 5 3 4 5 9 8

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

Sample Output

269

Sample Input

8

9 4 1 7 10 1 6 5

0 1 2 1 1 5 5 5

Sample Output

121

Comments

There are no comments at the moment.