SUMMAX4
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