마을 관람

면접 대비

시간 제한20초메모리 제한1024 MB

요약

마을의 미적 가치가 주어진 트리에서 등대를 세울 마을을 골라, 선택된 마을과 인접한 마을의 가치 합이 최대가 되도록 한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 트리, DFS, 그리디
정답자: 아직 제출이 없습니다

문제

킥스타티아의 시골에는 V개의 마을(1번부터 V번)이 있고, V-1개의 양방향 도로(1번부터 V-1번)로 연결되어 있다. i번 도로는 Xi번 마을과 Yi번 마을을 연결한다. 각 도로는 정확히 두 마을을 연결하며, 같은 두 마을을 연결하는 도로는 없다. 또한 킥스타티아의 어떤 두 마을을 연결하는 도로의 나열은 정확히 하나만 존재한다.

어떤 마을은 다른 마을보다 아름답다. i번 마을의 아름다움 값은 Bi이다. 아름다움 값이 음수인 마을도 있을 수 있다.

일부 마을에 등대를 세우려 한다. 어떤 마을에 등대가 세워져 있거나, 그 마을과 도로로 직접 연결된 마을에 등대가 세워져 있으면 그 마을은 밝혀진다.

등대는 원하는 만큼 많이 또는 적게(하나도 세우지 않아도 된다) 세울 수 있다. 밝혀진 마을의 아름다움 값 합의 최댓값은 얼마인가?

입력

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 마을의 수 V가 담긴 한 줄로 시작한다. 둘째 줄에는 V개의 정수가 주어진다. 이 중 i번째 정수는 i번 마을의 아름다움 값 Bi이다.

그다음 V-1개의 줄이 이어진다. i번째 줄에는 Xi와 Yi가 주어지며, i번 도로가 Xi번 마을과 Yi번 마을을 연결한다는 뜻이다.

출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 밝혀진 마을의 아름다움 값 합의 최댓값이다.

제한

1 ≤ T ≤ 100.
2 ≤ V ≤ 105.
모든 i에 대해 -105 ≤ Bi ≤ 105.
모든 i에 대해 1 ≤ Xi, Yi ≤ V.
모든 i에 대해 Xi ≠ Yi.
i ≠ j인 모든 i, j에 대해 (Xi, Yi) ≠ (Xj, Yj).
모든 마을 쌍을 연결하는 도로의 나열은 정확히 하나만 존재한다.

힌트

예제 케이스 #1에서는 2번과 7번 마을에 등대를 세울 수 있다. 그러면 2, 4, 5, 6, 7, 9번 마을이 밝혀지고, 아름다움 값 합은 4 + 8 + 20 + 30 + (-2) + 7 = 67이 된다. 같은 합을 얻는 다른 등대 배치도 있다.

예제 케이스 #2에서는 1, 2, 3번 마을에 등대를 세울 수 있다. 그러면 1, 2, 3, 4번 마을이 밝혀지고, 아름다움 값 합은 (-2) + 20 + 20 + 20 = 58이 된다. 같은 합을 얻는 다른 등대 배치도 있다.

예제 케이스 #3에서는 등대를 하나도 세우지 않는 것이 최선이다. 그러면 밝혀지는 마을이 없으므로 아름다움 값 합은 0이다.

예제1

예제 1

입력

3
9
-10 4 -10 8 20 30 -2 -3 7
1 4
2 4
4 3
9 4
9 8
7 5
6 7
7 9
4
-2 20 20 20
1 2
1 3
1 4
5
-5 -10 8 -7 -2
5 4
4 3
3 2
2 1

예상 출력

Case #1: 67
Case #2: 58
Case #3: 0