사과나무 > 문제은행

본문 바로가기


실전대비 Level5

1400 : 사과나무

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 9 회    시도횟수: 172 회   



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

 

한 마리의 벌레가 사과나무의 임의의 노드부터 움직이기 시작한다.
벌레가 어떤 노드에 위치해 있을 때, 이 벌레는 그 노드 안의 모든 사과를 먹을 수 있다.
사과를 다 먹은 후에 벌레는 나무의 가지를 따라 다른 노드로 이동한다.
만약 현재 노드에 연결된 노드들이 여러 개 있다면 그 중 하나를 임의로 택할 수 있으나 이미 방문했던 노드는 다시 방문할 수 없다.
더 이상 갈 수 있는 노드가 없을 때 벌레는 움직임을 종료한다.

 

사과나무가 주어졌을 때, 벌레가 먹을 수 있는 사과의 최대 개수와 벌레가 움직이기 시작하는 노드를 구해내는 프로그램을 작성하시오.


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

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


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

[Copy]
4 
1 
5 
5 
5 
1 2 
2 3 
2 4
[Copy]
15 3



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.