문제
용주는 우연히 산에서 보물을 하나 주웠다. 용주는 이 보물을 외딴 섬에 있는 동굴에 숨기기로 했다.
동굴은 크게 N개의 방이 있으며, N-1개의 통로로 이루어져 있다.
어떤 방에서든 모든 방으로 갈 수 있는 경로가 유일하게 존재한다.
x번 방과 y번 방의 거리란, x번 방에서 y번 방으로 가는 경로상에 있는 통로의 수라고 정의하도록 하자.
용주는 최근 보물찾기 1등을 달리고 있는 통칭 “해적형제” 의영-재영 형제가 동굴에서 보물을 찾을 때,
각각 두 가지 방식으로 찾는다는 것을 알아냈다.
탐색 방식은 아래와 같다.
- 의영이는 입구(1번 방)에서의 거리가 가장 가까운 방 순서대로 수색하되, 거리가 같은 방끼리는 번호가 작은 방부터 수색한다.
- 재영이는 입구(1번 방)에서의 거리가 가장 가까운 방 순서대로 수색하되, 거리가 같은 방끼리는 번호가 큰 방부터 수색한다.
- 방 하나를 탐색하는데는 1시간이 걸리며, 통로로 이동하는 시간은 너무 미미하므로 무시한다.
의영이와 재영이는 둘 중 한 명이 이미 탐색을 마친 방은 탐색하지 않고 다음 순서로 넘어간다.
- 동시에 같은 방을 탐색하게 될 경우엔 의영이가 맡게 되고 재영이는 다음 순서로 넘어간다.
예를 들어 그림 1과 같은 동굴이 있다고 하자.
그림 1
우선 탐색 방식의 이해를 돕기 위해, 의영이만 혼자 보물을 찾는다고 가정할 때 탐색 순서는
1->2->3->4->5->6->7->8이며, (1->2->3->4->5->6->8->7이 아님에 유의한다.)
재영이의 경우 1->4->3->2->8->7->6->5이다.
따라서 둘이 같이 탐색을 한다면 탐색순서는 다음과 같다.
용주는 자신이 보물을 숨긴 동굴에 의영-재영 형제가 도착하더라도 최대한 보물을 찾는데 오래 걸리게 만들어, 자신의 보물을 지킬 시간을 벌려고 한다.
그러려면 위 예의 경우에는 6번 방이나 7번 방에 보물을 숨겨야 최대한 오랜 시간인 4시간 동안 버틸 수 있다.
동굴의 구조가 주어졌을 때, 용주가 의영-재영에게 최대한 오래 버티기 위해 용주가 보물을 숨겨야 하는 최적의 방을 찾아 출력하는 프로그램을 작성하시오.
입력
첫 줄에 동굴에 있는 방의 개수인 N이 주어진다.(1≤N≤200,000)
다음 N-1개 줄에 걸쳐서 각 통로의 정보가 u, v의 형식으로 주어진다.(1≤u,v≤N)
이는 방 u와 방 v를 잇는 통로가 존재함을 뜻한다.
출력
최적의 방을 찾아 출력한다. 만약 그러한 방이 여러 개일 경우에는, 번호가 낮은 순서대로 공백을 사이에 두고 한 줄에 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 28점 | 어떤 방에 있어서도 연결된 통로가 최대 2개 이하이고, 1번방에 연결된 통로는 1개인 경우 |
| #2 | 64점 | N <= 1,000 |
| #3 | 8점 | 추가 제약 없음 |
예제
8
1 2
2 5
2 6
1 3
4 1
7 4
8 3
6 7
로그인해야 코드를 작성할 수 있어요.