You are not logged in. Please login at www.codechef.com to post your questions!

×

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: Link

asked 05 Oct '14, 10:12

orchidmajumder's gravatar image

3★orchidmajumder
3584815
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,182
×674
×469
×182
×6
×5

question asked: 05 Oct '14, 10:12

question was seen: 5,593 times

last updated: 05 Oct '14, 10:12