Informatica Online Judge

  여행 계획 [1239 / 04D7]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 13   Total Tried : 31


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

GSHS국은 V개의 도시를 가지고, V-1개의 도로들로 이 도시들이 연결되어 있다.

임의의 한 도시에서 다른 도시로는 항상 이동할 수 있는 길이 존재한다.

각 도시에는 그 도시의 평점이 정해져 있다. 평점이 높을 수록 재미있는 도시임을 알 수 있다.

경곽이는 임의의 한 도시에서 출발해서 임의의 한 도시에서 여행을 마칠 수 있다.

출발 도시에서 도착도시로 도로를 통해서 이동할 수 있으며, 한 번 지난 도시는 다시 지날 수 없다고 할 때, 경곽이가 여행한 도시들의 평점의 합을 최대화 하고 싶다.

경곽이가 재미있는 여행을 할 수 있도록 도와주자.

Input

첫 번째 줄에 도시의 수 V가 입력된다.

두 번째 줄에 각 V개의 도시의 평점이 공백으로 구분되어 입력된다. 평점은 0을 포함한 자연수이다. (즉, 음수일 수는 없다.)

세 번째 줄부터 V-1줄에 걸쳐서 각 도시를 연결하는 도로의 정보가 입력된다. 이 도로는 양방향으로 이동할 수 있는 도로이다.

[입력값의 정의역]
1 <= V <= 10,000

Output

여행한 도시들의 평점 합의 최댓값과 출발하는 도시의 번호를 출력한다.

단, 같은 최댓값을 가지는 여행의 방법이 여러 개 존재한다면, 그러한 출발 도시들 중 번호가 가장 작은 도시의 번호를 출력한다.

IO Example

입력
3
1 2 3
1 2
2 3

출력
6 1

* 설명 : 1번 - 2번 - 3번으로 여행하면 만족도가 6으로 가장 크다. 물론 3 - 2 - 1로 여행해도 6이지만 도시 번호가 1이 빠르므로 1을 출력한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]