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 ?
Thanks in advance.
P.S. Problem is not from currently running contest.
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.
Thank you for your response! To be honest I knew O(NlogN) complexity solution, but in editorial it was mentioned O(n) solution which used idea I mentioned above, I was just wondering how to make reverse order dynamic programming on tree ?
Link to the problem?
5th problem.
Memorize the result of dynamic programming by the pair
(v, par). There are about 3N possible pairs.What you mean by saying pair (v,par) what par does mean? And how can it help me to calculate diameter of the trimmed tree ?
Say, we have standard function
dfs(v, par)calculating diameter of the tree rooted invand given directionpar(parent) →v→ children ofv.To compute desired value one has to take
max(dfs(child_v, v), max1 + max2 + 2)theremax1andmax2are the first and the second maximum depth ofv's childs.Function
depth(v, par)works in the similar way.So, we only have to calculate
dfs(v, par)anddepth(v, par)2 times for every direction of every edge and N times for(v, -1).Thank you very much, that is what I wanted !