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.