문제
사과나무란 각 노드 안에 사과가 담겨있는 트리이다. 각 노드에 담겨있는 사과의 개수는 다를 수 있으며, 0일 수도 있다.
한 마리의 벌레가 사과나무의 임의의 노드부터 움직이기 시작한다. 벌레가 어떤 노드에 위치해 있을 때, 이 벌레는 그 노드 안의 모든 사과를 먹을 수 있다. 사과를 다 먹은 후에 벌레는 나무의 가지를 따라 다른 노드로 이동한다. 만약 현재 노드에 연결된 노드들이 여러 개 있다면 그 중 하나를 임의로 택할 수 있으나 이미 방문했던 노드는 다시 방문할 수 없다. 더 이상 갈 수 있는 노드가 없을 때 벌레는 움직임을 종료한다.
사과나무가 주어졌을 때, 벌레가 먹을 수 있는 사과의 최대 개수와 벌레가 움직이기 시작하는 노드를 구해내는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 사과나무의 노드 수를 나타내는 자연수 n(1≤n≤10,000)이 주어진다.
다음 줄에는 1번부터 n번까지의 노드에 들어있는 사과의 개수가 차례대로 주어진다. 사과의 전체 개수는 231-1 범위를 넘지 않는다.
다음 n-1개의 줄에는 서로 다른 두 정수 A, B(1≤A, B≤n)이 주어진다. 이는 A번 노드와 B번 노드를 연결하는 가지가 존재한다는 의미이다.
출력
입력 데이터에 대해서 벌레가 먹을 수 있는 사과의 최대 개수와 벌레가 시작해야 하는 노드의 번호를 출력한다.
만 약 가능한 출발 노드가 여러개일 수 있다면 그 중 번호가 제일 작은 것을 출력한다.
예제
4
1
5
5
5
1 2
2 3
2 4
15 3
로그인해야 코드를 작성할 수 있어요.