Algorithms and Data Structures

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.


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.


The program should print the centroid of the given tree. If there are several possible answers, the program can print any of them.


3 1 2 1 3
5 1 2 2 3 3 4 3 5
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).


Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue