#2612 Apple Tree

2 s   64 MB  

Description

사과나무란 각 노드 안에 사과가 담겨있는 트리이다. 각 노드에 담겨있는 사과의 개수는 다를 수 있으며, $0$일 수도 있다.

한 마리의 벌레가 사과나무의 임의의 노드부터 움직이기 시작한다. 벌레가 어떤 노드에 위치해 있을 때, 이 벌레는 그 노드 안의 모든 사과를 먹을 수 있다. 사과를 다 먹은 후에 벌레는 나무의 가지를 따라 다른 노드로 이동한다.

만약 현재 노드에 연결된 노드들이 여러 개 있다면 그 중 하나를 임의로 택할 수 있으나 이미 방문했던 노드는 다시 방문할 수 없다. 더 이상 갈 수 있는 노드가 없을 때 벌레는 움직임을 종료한다. 사과나무가 주어졌을 때, 벌레가 먹을 수 있는 사과의 최대 개수와 벌레가 움직이기 시작하는 노드를 구해내는 프로그램을 작성하시오.

Input

입력은 여러 데이터로 구성된다.

첫째 줄에는 사과나무의 노드 수를 나타내는 자연수 $n(1 \leq n \leq 10,000)$이 주어진다. 다음 줄에는 $1$번부터 $n$번까지의 노드에 들어있는 사과의 개수가 차례대로 주어진다.

사과의 전체 개수는 signed 32-bit integer 범위를 넘지 않는다. 다음 $n-1$개의 줄에는 서로 다른 두 정수 $A, B(1 \leq A, B \leq n)$ 이 주어진다. 이는 $A$번 노드와 $B$번 노드를 연결하는 가지가 존재한다는 의미이다.

입력은 $n=0$일 때 끝난다.

Output

각각의 데이터에 대해서, 벌레가 먹을 수 있는 사과의 최대 개수와 벌레가 시작해야 하는 노드의 번호를 출력한다. 만약 가능한 출발 노드가 여러개일 수 있다면 그 중 번호가 제일 작은 것을 출력한다.

Sample Input

Sample Output

2
1
2
1 2
3
1
2
3
1 3
3 2
4
1
5
5
5
1 2
2 3
2 4
0 
3 1
6 1
15 3

Source

0th SNUPC