나무 위의 벌레

트리는 사이클이 없는 연결 그래프이다. 이 문제에서 다루는 나무는 루트가 없는 트리이다. 각 간선은 가지를, 각 정점은 열매가 달릴 수 있는 지점을 나타낸다. 어떤 정점에는 열매가 0개 달려 있을 수도 있다.

나무 위에는 벌레 한 마리가 있다. 벌레는 임의의 정점에서 이동을 시작할 수 있다. 벌레가 어떤 정점에 도착하면 그 정점에 있는 열매를 모두 먹는다. 그런 다음 아직 지나가지 않은 인접한 간선이 있다면, 그중 하나를 골라 다른 정점으로 이동한다. 한 번 지난 간선은 다시 지날 수 없다. 그래프가 트리이므로 벌레의 이동 경로는 단순 경로가 되며, 더 이상 지나갈 수 있는 간선이 없는 정점에서 이동이 끝난다.

나무의 모양과 각 정점에 달린 열매의 수가 주어졌을 때, 벌레가 먹을 수 있는 열매의 최대 개수와 그 최대값을 얻기 위해 이동을 시작해야 하는 정점을 구하시오. 가능한 시작 정점이 여러 개라면 번호가 가장 작은 정점을 선택한다.

첫째 줄에 트리의 정점 수를 나타내는 정수 n (1 <= n <= 10,000)이 주어진다.

다음 줄에는 n개의 정수가 주어진다. i번째 정수는 i번 정점에 달린 열매의 개수이다.

다음 n - 1개의 줄에는 두 정수 A, B (1 <= A, B <= n)가 주어진다. 이는 A번 정점과 B번 정점이 간선으로 연결되어 있음을 의미한다.

나무에 달린 열매의 총 개수는 2^31 - 1 (2,147,483,647)개를 넘지 않는다.

첫째 줄에 벌레가 먹을 수 있는 열매의 최대 개수와, 그때 이동을 시작할 정점의 번호를 출력한다.

답이 여러 개라면 정점 번호가 가장 작은 경우를 출력한다.