마을 구경하기

Kickstartia의 시골 지역은 1부터 V까지 번호가 붙은 V개의 마을과, 1부터 V-1까지 번호가 붙은 V-1개의 양방향 도로로 이루어져 있다. i번째 도로는 마을 $X_{i}$와 마을 $Y_{i}$를 연결한다. 각 도로는 정확히 두 마을을 연결하며, 같은 두 마을을 연결하는 도로가 둘 이상 존재하지 않는다. 또한 Kickstartia의 임의의 두 마을을 연결하는 도로의 순서는 정확히 하나 존재한다.

어떤 마을은 다른 마을보다 더 아름답다. i번째 마을의 아름다움 값은 $B_{i}$이다. 마을의 아름다움 값이 음수일 수도 있음에 유의한다!

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

등대는 원하는 만큼 많이 또는 적게 세울 수 있으며, 하나도 세우지 않아도 된다. 빛을 받는 마을들의 아름다움 값의 합으로 얻을 수 있는 최댓값은 얼마인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 2 ≤ V ≤ $10^{5}$. 모든 i에 대해 -$10^{5}$ ≤ $B_{i}$ ≤ $10^{5}$. 모든 i에 대해 1 ≤ $X_{i}$, $Y_{i}$ ≤ V. 모든 i에 대해 $X_{i}$ ≠ $Y_{i}$. 모든 i ≠ j에 대해 ($X_{i}$, $Y_{i}$) ≠ ($X_{j}$, $Y_{j}$). 모든 마을 쌍을 연결하는 도로의 순서는 정확히 하나 존재한다.

테스트 세트 1 (공개)

1 ≤ V ≤ 15.

테스트 세트 2 (비공개)

1 ≤ V ≤ $10^{5}$.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 마을의 수인 정수 V가 포함된 줄로 시작한다. 둘째 줄에는 V개의 정수가 주어진다. 이 중 i번째 정수는 i번째 마을의 아름다움 값인 $B_{i}$이다.

이어서 V-1개의 줄이 주어진다. i번째 줄에는 $X_{i}$와 $Y_{i}$가 주어지며, 이는 i번째 도로가 마을 $X_{i}$와 마을 $Y_{i}$를 연결함을 나타낸다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 빛을 받는 마을들의 아름다움 값의 합으로 얻을 수 있는 최댓값이다.

예제 케이스 #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이다.