Trò chơi bóng

Công ty phát triển trò chơi $X$ đang thiết kế một trò chơi mới trên điện thoại và hiện đang trong giai đoạn thử nghiệm. Mỗi màn chơi gồm có $N$ vị trí, vị trí $i$ ($1 \leq i \leq N$) có điểm thưởng là $a_i$.

$N$ vị trí này nằm ở các độ cao khác nhau và được nối với nhau bởi $N - 1$ con đường. Vị trí $i$ sẽ dẫn tới vị trí $P_i$, và mọi vị trí cuối cùng đều đổ dồn về vị trí gốc là vị trí $1$ ($P_1 = 0$).

Tại mỗi vị trí không có vị trí nào khác dẫn tới nó sẽ có một chiếc xe gắn nam châm. Trong quá trình xe di chuyển xuống, người chơi có thể bật công tắc để kích hoạt nam châm. Khi đó, nam châm sẽ bắt đầu hút toàn bộ điểm thưởng tại các vị trí trên đường nó đi qua cho đến khi về tới vị trí $1$. Công tắc chỉ được bật duy nhất một lần và không thể tắt. Số điểm người chơi nhận được từ chiếc xe là điểm thưởng lớn nhất trong số các vị trí mà nam châm đã hút được. Điểm thưởng tại các vị trí bị hút còn lại sẽ bị mất đi (không thể thu thập lại ở các lượt sau).

Người chơi có thể chọn đẩy các xe theo một thứ tự bất kỳ sao cho tổng điểm nhận được là lớn nhất có thể. Bạn hãy tìm chiến lược tối ưu để đạt điểm số cao nhất cho mỗi màn chơi nhằm giúp công ty đánh giá độ khó của trò chơi.

Đầu vào:

• Dòng đầu tiên chứa một số nguyên dương $N$ ($1 \leq N \leq 10^5$).
• Dòng thứ hai chứa mảng $P$ gồm $N$ phần tử, trong đó $P_i$ là vị trí mà vị trí $i$ dẫn tới ($P_1 = 0$ và $1 \leq P_i \leq N, \forall 2 \leq i \leq N$).
• Dòng thứ ba chứa mảng $a$ gồm $N$ phần tử là điểm thưởng tại các vị trí ($1 \leq a_i \leq 10^9, \forall 1 \leq i \leq N$).

Ràng buộc:

• 40% số test có $N \leq 1000$.
• 60% số test còn lại không có ràng buộc gì thêm.

Đầu ra:

• Dòng đầu tiên chứa một số nguyên dương $X$ — số điểm tối đa mà người chơi có thể đạt được.
• Dòng thứ hai chứa các số nguyên dương biểu thị vị trí xuất phát của các xe được đẩy xuống theo đúng thứ tự thực hiện để đạt điểm tối đa.
• Dòng thứ ba chứa các số nguyên tương ứng với vị trí bắt đầu bật công tắc nam châm của từng xe theo đúng thứ tự ở dòng 2.
• Nếu có nhiều phương án tối ưu, chỉ cần in ra một phương án bất kỳ.

Giải thích:

• Ở ví dụ 1, có 2 vị trí đặt xe là 2 và 3.
  • Nếu đẩy xe 2 trước và bật công tắc từ vị trí 2: xe sẽ di chuyển từ 2 về 1, hút điểm ở 2 vị trí này là 60 và 100; số điểm cao nhất là 100 nên người chơi nhận được 100 điểm. Sau đó đẩy xe 3 và bật công tắc từ vị trí 3: xe sẽ đi qua các vị trí 3, 4 và 1; số điểm hút được lần lượt là 80, 30 và 0 (điểm ở vị trí 1 đã bị lấy ở lượt trước), số điểm nhận được là 80. Tổng điểm đạt được là $100 + 80 = 180$.
  • Nếu đẩy xe 3 trước và bật công tắc từ vị trí 3: xe đi qua các vị trí 3, 4, 1 và nhận được 100 điểm. Sau đó đẩy xe 2 và bật công tắc từ vị trí 2: xe đi qua các vị trí 2, 1 và chỉ nhận được 60 điểm (vì điểm ở vị trí 1 đã bị lấy trước đó). Tổng điểm đạt được là $100 + 60 = 160$.
  • Do đó, phương án tối ưu là đẩy lần lượt các xe 2 và 3, đồng thời bật công tắc ngay tại vị trí xuất phát để đạt tổng điểm là 180. Ngoài ra còn một cách khác là bật công tắc cho xe thứ hai tại vị trí 1.

• Ở ví dụ 2, có nhiều cách để đạt được điểm tối đa, chẳng hạn: $\{3, 4, 6, 7, 8\}$, $\{4, 3, 6, 8, 7\}$, $\{3, 6, 8, 7, 4\}$,... Dưới đây là hình ảnh minh họa cho thứ tự đẩy $\{3, 6, 8, 4, 7\}$ với công tắc được bật ngay từ vị trí xuất phát:

Ví dụ 1:

Đầu vào:

4
0 1 4 1
100 60 80 30

Đầu ra:

180
2 3
2 3

Ví dụ 2:

Đầu vào:

8
0 1 1 1 2 2 5 5
10 10 7 7 10 5 10 10

Đầu ra:

47
3 6 8 4 7
3 6 8 4 7