연쇄 반응

Wile은 사막에서 혼자 살면서, 연쇄 반응으로 움직이는 복잡한 기계를 만들어 시간을 보낸다. 각 기계는 $1,2,\dots,N$ 번호가 붙은 $N$개의 모듈로 이루어진다. 각 모듈은 번호가 더 작은 다른 모듈 하나를 가리킬 수 있다. 가리키는 모듈이 없으면 심연을 가리킨다.

다른 모듈이 가리키지 않는 모듈을 시작 모듈(initiator)이라고 한다. Wile은 시작 모듈을 직접 작동시킬 수 있다. 모듈이 작동하면 그 모듈이 가리키는 모듈을 작동시키고, 그 모듈은 다시 자신이 가리키는 모듈을 작동시킨다. 이 과정은 연쇄가 심연에 닿거나 이미 작동한 모듈에 닿을 때까지 이어진다. 이를 연쇄 반응이라고 한다.

각 모듈에는 재미 지수 $F_i$가 있다. Wile이 연쇄 반응으로 얻는 재미는 그 연쇄 반응에서 작동한 모든 모듈의 재미 지수 중 최댓값이다. Wile은 각 시작 모듈을 한 번씩 정한 순서대로 작동시킨다. 세션 전체의 재미는 Wile이 각 연쇄 반응에서 얻은 재미의 합이다.

예를 들어 Wile에게 재미 지수가 $F_1=60$, $F_2=20$, $F_3=40$, $F_4=50$인 모듈 4개가 있다고 하자. 모듈 1은 심연을 가리키고, 모듈 2와 3은 모듈 1을, 모듈 4는 모듈 2를 가리킨다. 시작 모듈은 3과 4 두 개이며, Wile은 이 둘을 어떤 순서로든 작동시켜야 한다.

위 그림처럼 Wile이 모듈 4를 먼저 작동시키면 모듈 4, 2, 1이 같은 연쇄 반응에서 작동하고, 재미는 $\max(50,20,60)=60$이다. 그다음 모듈 3을 작동시키면 모듈 3만 작동한다(모듈 1은 다시 작동할 수 없다). 재미는 40이고, 세션 전체의 재미는 $60+40=100$이다.

반대로 Wile이 모듈 3을 먼저 작동시키면 모듈 3과 1이 같은 연쇄 반응에서 작동하고, 재미는 $\max(40,60)=60$이다. 그다음 모듈 4를 작동시키면 모듈 4와 2가 같은 연쇄 반응에서 작동하고, 재미는 $\max(50,20)=50$이다. 세션 전체의 재미는 $60+50=110$이다.

모듈의 재미 지수와 연결 구조가 주어졌을 때, Wile이 시작 모듈을 가장 좋은 순서로 작동시켰을 때 얻을 수 있는 최대 재미를 구하라.

입력의 첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 3줄로 나타난다. 각 테스트 케이스의 첫 줄에는 Wile이 가진 모듈의 개수 $N$이 주어진다. 둘째 줄에는 $N$개의 정수 $F_1,F_2,\dots,F_N$이 주어진다. $F_i$는 $i$번 모듈의 재미 지수이다. 셋째 줄에는 $N$개의 정수 $P_1,P_2,\dots,P_N$이 주어진다. $P_i=0$이면 모듈 $i$는 심연을 가리킨다. 그렇지 않으면 모듈 $i$는 모듈 $P_i$를 가리킨다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 Wile이 시작 모듈을 가장 좋은 순서로 직접 작동시켰을 때 얻을 수 있는 최대 재미이다.

• $1≤T≤100$.
• $1≤F_i≤10^9$.
• $0≤P_i≤i-1$, 모든 $i$에 대하여.

샘플 케이스 #1은 문제 설명에서 다룬 경우이다.

샘플 케이스 #2에는 시작 모듈이 4개(모듈 2부터 5까지) 있으므로 연쇄 반응도 4개이다. 순서를 3, 5, 4, 2로 하여 작동시키면 재미가 각각 3, 5, 4, 2인 연쇄 반응이 생기고, 전체 재미는 14이다. 입력에서 가장 큰 재미 네 개의 합이므로 이 값보다 큰 재미는 얻을 수 없다.

샘플 케이스 #3에서 시작 모듈 5개를 작동시키는 최적 순서는 4, 5, 7, 6, 8이다.