#856. SUMMAX4 - Tổng lớn nhất trên cây

Cho đồ thị dạng cây gồm đỉnh, các đỉnh được đánh số từ đến , mỗi đỉnh được gán một số nguyên dương . Gọi là khoảng cách giữa hai đỉ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à

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

Dữ liệu vào:

• Dòng đầu tiên ghi số là số đỉnh của cây;
• Dòng tiếp theo ghi số nguyên dương là các số được gán với các đỉnh theo thứ tự;
• Dòng tiếp theo có số thể hiện có đường đi từ đỉnh đến với ( thì đỉnh là gốc cây).

Dữ liệu ra:

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

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

269

Dữ liệu vào:

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

Dữ liệu ra:

121

Giới hạn:

• .