Find the Centroid of a Tree
You are given a tree with
v vertices and your task is to find the centroid of the tree. The centroid of a tree is a vertex such that when it is removed, all the remaining subtrees have a size of at most nodes.Input
The first line of the input contains a single integer
v (1 ≤ v ≤ 100 000).The following
v-1 lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.Output
The program should print the centroid of the given tree. If there are several possible answers, the program can print any of them.
Examples
Input | Output |
3
1 2
1 3 | 1 |
5
1 2
2 3
3 4
3 5 | 3 |
Hint
You can calculate the size of the subtree for each node (the number of child nodes).
Then, check for all the subtrees of each node if their size is smaller or equal to half of the vertices in the whole tree (all the child nodes and
v-currentNodeSize to account for the parent subtree).Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB