shank_punk's blog

By shank_punk, 9 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.