### lth's blog

By lth, 6 years ago, Hi guys.
I am trying to solve the following problem :
Given a tree, you must remove an edge and add an edge so that the new tree is connected and diameter of the new tree is smallest possible. Number of vertices are up to 300000.
When I remove any edge (u,v) I got 2 new trees: one rooted at v and one for which u is leaf. It is obvious that smallest diameter I can achieve is max{d(first tree),d(second tree),d(firs_tree)/2+d(second_tree)/2+1}. Now I can traverse over all edges and remove them and take minimum of those values. Now problem is: I can calculate the diameter of the hanging tree just using dynamic programming on the tree, but I am somehow in trouble of calculating the diameter of the trimmed tree. It seems it is also possible to calculate the diameter of the trimmed tree using dynamic programming but in opposite order, I mean from leaves to root or somehow, but I don't know how exactly to do that. Can anyone help me or give me some hints ? tree, Comments (8)
 » 6 years ago, # | ← Rev. 6 →   Suppose that we want to calculate diameter of some subtree. We can use the following approach.We can prove that . Where d1 and d2 are fartest vertexes. So we can create a dynamic data structer which allow us to do two operations : insert a vertex ask for diameter. We will create an in order travel of the tree where any subtree will denote a interval. After then while removing a edge we can calculate diameter of fixed subtree(the one leaving from the tree). Because it denotes a single interval. Also other part of the tree denotes atmost two interval. Create a segment tree which allows to do above two operations. Overall complexity is O(NlogN) if we can query lca O(1).(which can be done with RMQ). PS: I have realized this solution is way too much compilcated comparing to the dynamic programming one but i think it is somehow interesting anyway.
•  » » » Memorize the result of dynamic programming by the pair (v, par). There are about 3N possible pairs.
•  » » » » » Say, we have standard function dfs(v, par) calculating diameter of the tree rooted in v and given direction par (parent)  →  v  →  children of v. To compute desired value one has to take max(dfs(child_v, v), max1 + max2 + 2) there max1 and max2 are the first and the second maximum depth of v's childs. Function depth(v, par) works in the similar way. So, we only have to calculate dfs(v, par) and depth(v, par) 2 times for every direction of every edge and N times for (v, -1).