The Centroid

Difficulty: 1800 6000 ms 128 MB

dp trees

The centroid of a tree is a node whose removal leaves all remaining components with at most N/2 nodes. Print the centroid with the smallest index (there may be one or two centroids).

Input: the first line has N; the next N−1 lines have the edges.

Output: the smallest-indexed centroid.

Constraints:

• 1 ≤ N ≤ 10⁵

Sample Tests

4
1 2
2 3
2 4

2

1

1

Read the Editorial