Informatica Online Judge

  트리의 중심 [2104 / 0838]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 12   Total Tried : 41


The Champion of this Problem (C++) : ajou709 - 78ms / 746byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16028]

Background

사이클이 없는 N개의 노드로 이루어진 트리가 있다.
이 트리의 중심을 찾으려고 한다.
트리의 중심이란 그 점을 root로 잡을때 트리의 깊이가 최소가 되는 점을 말한다.
주어진 트리에서 트리의 중심을 찾으시오.
단, 트리의 중심은 유일함이 보장된다.

Input

첫 줄에 노드의 개수 N 이 입력된다. $(1<= N <= 500,000)$
이후 N-1개의 줄에 연결된 두 노드의 정보가 입력된다.

Output

트리의 중심의 번호를 출력한다.

IO Example

입력예제 1

3
1 2
2 3

출력예제 1

2

입력예제 2

8
1 2
1 3
3 4
3 5
2 8
6 2
7 2

출력예제 2

1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]