아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

윌로우

시간 제한5초메모리 제한512 MB

요약
동전이 놓인 트리에서 두 명이 시작 도시를 정한 뒤 도로를 한 번씩만 써서 도시를 번갈아 수집하고 하나아가 최종 점수 차이를 최대화합니다.
난이도

어려움10점 중 9점

유형
게임 이론, 트리, 동적 계획법
정답자
아직 제출이 없습니다

문제

Hanaa와 Sherine이 윌로우(Willow)라는 게임을 한다. 게임판에는 도시가 NN개 있고, ii번 도시에는 동전이 CiC_i개 놓여 있다. 도시 사이에는 양방향 도로가 N−1N - 1개 있으며, 어느 도시에서든 나머지 모든 도시로 갈 수 있다.

먼저 Hanaa가 출발할 도시를 하나 고른다. 그다음 Sherine이 그 선택을 보고 자기가 출발할 도시를 고르는데, Hanaa가 고른 도시를 그대로 골라도 된다. 그 뒤 Hanaa부터 번갈아 차례를 진행한다.

자기 차례가 되면 지금 서 있는 도시에 남아 있는 동전을 모두 가져간다. 그 도시에 처음부터 동전이 없었거나 이미 누군가 그 도시에서 차례를 시작했다면 가져갈 동전이 없다. 그다음 아직 쓰지 않은 도로가 남아 있으면 그중 하나를 따라 이웃 도시로 반드시 이동한다. 쓸 수 있는 도로가 없으면 그 자리에 머무른다. 도로는 하나당 한 번만 쓸 수 있어서, 한 사람이 지나간 도로는 다른 사람도 다시 쓸 수 없다. 두 사람 모두 가져갈 동전이 없고 이동도 할 수 없게 되면 게임이 끝난다.

게임이 끝나면 각자의 점수는 자기가 모은 동전 수에서 상대가 모은 동전 수를 뺀 값이다. 상대가 더 많이 모았으면 점수는 음수가 된다. 두 사람 모두 자기 점수를 최대로 만들려고 한다. 둘 다 최선을 다해 겨룰 때 Hanaa가 얻을 수 있는 점수의 최댓값을 구하라.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다. 이어서 테스트 케이스가 TT개 주어진다.

각 테스트 케이스의 첫 줄에는 도시의 수 NN이 주어진다. 다음 NN개 줄 가운데 ii번째 줄에는 ii번 도시에 놓인 동전 수 CiC_i가 주어진다. 이어지는 N−1N - 1개 줄 가운데 ii번째 줄(ii는 1부터 센다)에는 정수 jj가 하나 주어지며, 이는 ii번 도시와 jj번 도시를 잇는 도로가 있다는 뜻이다. 항상 1≤i<j≤N1 \le i < j \le N이고, 게임을 시작할 때 어느 도시에서든 나머지 모든 도시로 갈 수 있다.

제한은 다음과 같다.

  • 1≤T≤501 \le T \le 50
  • 2≤N≤802 \le N \le 80
  • 0≤Ci≤100000 \le C_i \le 10000

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 Hanaa가 얻을 수 있는 점수의 최댓값이다.

예제1

  1. 예제 1

    입력
    3
3
1000
200
1000
2
3
8
8
0
8
0
0
0
0
10
2
5
4
5
6
7
8
10
150
200
0
5000
0
100
0
0
0
10000
10
3
8
5
8
7
8
9
10
    예상 출력
    Case #1: 200
Case #2: -2
Case #3: 5100