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

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

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.

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.