SRM 635 div II 1000 ptr.

I saw a post last night regarding Div II 1000 ptr. but could not find it now.
So, here is my approach to solve the Div II 1000 ptr problem from SRM 635 (this idea is mostly based on a comment of @xellos0 on topcoder forum).

You have n-1 edges to deal with. In every turn, you remove one edge say (X–Y). Then, the tree is broken into two subtrees one with root X and another with root Y. Now, find diameter of both the subtrees individually; say it’s d1 and d2. There should be one edge with the same cost as of edge (X–Y) that should be added between the two subtrees to make it a tree again (it does not matter which endpoints we connect while adding this edge, as the cost remains same). So, diameter of the new tree becomes d1+d2+cost[X][Y]. We take maximum over all such diameters and the initial diameter.

Finding diameter is a well known problem.
Problem on SPOJ

The idea is to run a DFS/BFS from any chosen vertex(here the vertex is fixed as we are dealing the problem in such a way that the tree is broken into two subtrees with root X and Y) and find the farthest vertex; call it Z. Now from Z, run a second dfs/bfs to find the farthest vertex and take max distance between these two paths (root to Z and from Z to farthest_from_z).

Here is an implementation:

1 Like