uva 10459 - Find all the best and worst roots of an undirected unweighted tree.

general
, , ,
1

Given an undirected tree, how can I find out those vertices which when taken as the root of the tree will minimize the depth of the tree. Similarly, I want to find those vertices which when taken as the root of tree, will maximize the depth of tree. I want to answer this for a general tree in linear time. (Linear in the number of vertices of the tree)

Uva 10459 link to the question

1 Like
2

Just think about the diameter of the tree and you will find an easy solution in O(N^2) which I believe it’s enough to pass the TL.

3

Find Diameter of the tree in two passes. Mid points will be the best vertices. then DFS to the farthest nodes(i.e worst nodes). Linear time. O(N^2) will TLE.