#851. SUMMAX2 - 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 , đỉnh số là gốc cây, mỗi đỉnh được gán một số nguyên dương . Ta có thể chọn nhiều đỉnh trên cây, tuy nhiên không được chọn hai đỉnh kề nhau. Hỏi với cách chọn như vậy thì tổng các số lớn nhất có thể nhận được là bao nhiêu?

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 ( vì đỉnh là gốc cây).

Dữ liệu ra:

• Ghi ra một số duy nhất là tổng lớn nhất tìm được.

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:

41

Giới hạn:

• .