### shank_punk's blog

By shank_punk, 7 years ago, Note : I am posting this question because the problem link has been removed . ****

If we are given a tree and asked to pick a node as the 'root' node such that the distance between the root and all leaf node is minimum , how do we pick the root ?

We should just print the distance from the root to leaf .

EG : 0->1->2 , we should pick 1 because the distance from 1 to 0 = 1 and distance from 1 to 2 = 1 . We can't pick 0 or 2 because the diatance will be 2 .

Constrains : number of nodes : 100000 value of each node 1<=ai<=100000

Input format : The first line contains N , the number of edges , the following N lines contains two numbers x and y denoting an edge from x to y .

Input : 4

1 2

2 3

2 4

3 4

Output: 2

My wrong solution  Comments (2)
 » The node that you need to pick is the center of the tree, as the tree is unweighted the maximum distance between the center of the tree to any leaf will be (diameter + 1) / 2 (integer division).PD: I think that the input is wrong, if the tree has N nodes it must have N — 1 edges.
•  » » Thanks , I have updated the question .