Wile sống một mình trong sa mạc, nên tự giải trí bằng cách chế tạo những cỗ máy phức tạp vận hành theo phản ứng dây chuyền. Mỗi máy gồm \(N\) mô-đun được đánh số \(1,2,\ldots,N\). Mỗi mô-đun có thể trỏ đến một mô-đun khác có chỉ số nhỏ hơn; nếu không, nó trỏ vào vực thẳm.

Những mô-đun không bị bất kỳ mô-đun nào khác trỏ đến được gọi là bộ khởi phát. Wile có thể kích hoạt thủ công các bộ khởi phát. Khi một mô-đun được kích hoạt, nó kích hoạt mô-đun mà nó trỏ tới nếu có; mô-đun đó có thể tiếp tục kích hoạt mô-đun thứ ba, và cứ thế cho đến khi chuỗi sắp chạm vực thẳm hoặc một mô-đun đã được kích hoạt. Quá trình này được gọi là một phản ứng dây chuyền.

Mỗi mô-đun \(i\) có hệ số vui \(F_i\). Mức vui Wile nhận được từ một phản ứng dây chuyền là hệ số vui lớn nhất trong số các mô-đun được kích hoạt trong phản ứng đó. Wile sẽ kích hoạt mỗi bộ khởi phát đúng một lần theo một thứ tự nào đó. Tổng mức vui của cả buổi là tổng mức vui từ từng phản ứng dây chuyền.

Ví dụ, giả sử Wile có \(4\) mô-đun với \(F_1=60,F_2=20,F_3=40,F_4=50\); mô-đun \(1\) trỏ vào vực thẳm, các mô-đun \(2\) và \(3\) trỏ đến mô-đun \(1\), còn mô-đun \(4\) trỏ đến mô-đun \(2\). Có hai bộ khởi phát, là \(3\) và \(4\), mà Wile phải kích hoạt theo một thứ tự nào đó.

Như hình trên, nếu Wile kích hoạt thủ công mô-đun \(4\) trước, các mô-đun \(4,2,1\) được kích hoạt trong cùng phản ứng dây chuyền, cho mức vui \(\max(50,20,60)=60\). Sau đó, khi Wile kích hoạt mô-đun \(3\), chỉ riêng mô-đun \(3\) được kích hoạt vì mô-đun \(1\) không thể kích hoạt lại, cho mức vui \(40\). Tổng mức vui là \(60+40=100\).

Tuy nhiên, nếu Wile kích hoạt mô-đun \(3\) trước, các mô-đun \(3\) và \(1\) được kích hoạt trong cùng phản ứng, cho mức vui \(\max(40,60)=60\). Sau đó, khi kích hoạt mô-đun \(4\), các mô-đun \(4\) và \(2\) được kích hoạt trong cùng phản ứng, cho mức vui \(\max(50,20)=50\). Tổng mức vui là \(60+50=110\).

Cho các hệ số vui và cách nối các mô-đun, hãy tính mức vui lớn nhất Wile có thể nhận được nếu kích hoạt các bộ khởi phát theo thứ tự tốt nhất.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Sau đó là \(T\) bộ test, mỗi bộ được mô tả bằng ba dòng. Dòng đầu chứa số nguyên \(N\), số mô-đun của Wile. Dòng thứ hai chứa \(N\) số nguyên \(F_1,F_2,\ldots,F_N\), trong đó \(F_i\) là hệ số vui của mô-đun thứ \(i\).

Dòng thứ ba chứa \(N\) số nguyên \(P_1,P_2,\ldots,P_N\). Nếu \(P_i=0\), mô-đun \(i\) trỏ vào vực thẳm; nếu không, mô-đun \(i\) trỏ đến mô-đun \(P_i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), và \(y\) là mức vui lớn nhất Wile có thể nhận được khi kích hoạt thủ công các bộ khởi phát theo thứ tự tốt nhất.

Ràng buộc

• \(1\le T\le100\).
• \(1\le F_i\le10^9\).
• \(0\le P_i\le i-1\) với mọi \(i\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(1\le N\le10\).
• Test Set 2 (phán quyết hiển thị): \(1\le N\le1000\).
• Test Set 3 (phán quyết ẩn): \(1\le N\le100000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
4
60 20 40 50
0 1 1 2
5
3 2 1 4 5
0 1 1 1 0
8
100 100 100 90 80 100 90 100
0 1 2 1 2 3 1 3

Case #1: 110
Case #2: 14
Case #3: 490

Nguồn

Google Code Jam 2022, Vòng loại, bài Chain Reactions.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.