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

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho đồ thị dạng cây gồm N đỉnh, các đỉnh được đánh số từ 1 đến N , đỉnh số 1 là gốc cây, mỗi đỉnh i được gán một số nguyên dương a_i . 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ố N là số đỉnh của cây;
  • Dòng tiếp theo ghi N số nguyên dương a_1, a_2, \ldots, a_N là các số được gán với các đỉnh theo thứ tự;
  • Dòng tiếp theo có N số p_1, p_2, \ldots, p_N thể hiện có đường đi từ đỉnh i đến p_i với 0\le p_i \le N ( p_1=0 vì đỉnh 1 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:

  • N \le 2\times 10^5; a_i \le 10^9 .