Algorithms and Data Structures

Find the Center of a Tree

You are given n cities that are connected to each other with n-1 roads. All the cities are connected to each other (maybe through other cities). You would like to make sure the capital is at the best possible location.
You decide that the best location is the one that minimizes the furthest distance from the borderline cities (the cities that are only connected to 1 city). Which cities would be the best candidates for the capital?


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 best candidates for the capital in increasing order.


4 1 2 2 3 3 4
2 3


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