I have a tree, and if I remove an edge the tree would get disconnected into 2 subtrees. Now, for each of these 2 subtrees I would like to find (quickly) 2 end nodes of a diameter, that is, I would like to find the end nodes of a diameter of subtree 1 and the end nodes of a diameter of subtree 2 (4 nodes in total). I need to do this for many possible edges (edge removals don't accumulate). Is it possible to do that efficiently? I need this in order to solve this problem. Otherwise I will need to figure out another approach. Thank you in advance.

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).Hello, I know a way to solve this offline. First of all, suppose you root the tree at node 1. Now, you can calculate de depth of each node. Suppose we are given a query so you have 2 nodes u and v. Now suppose depth[u] > depth[v]. To find the diameter of this subtree is easy and can be done using a simple dfs (call this dfs_up).

How? well, there are 2 ways for the diameter of the subtree of u. For the first option, it is on some subtree of u children and for the second it crosses node u. So for the first option, you just need to have the maximum subtree than can be achieved in children. For the second you need the 2 farthest nodes (which are actually leaves) from node u, and they can make a diameter by crossing u. (you can refer this and generalize the idea for non-binary trees). So suppose that at this point you have a tuple array called

`diam_up`

which contains, (leaf1, leaf2, distance) that is the 2 leaves that form the diameter, and the distance.Now the problem is how you calculate the diameter for the subtree of v (since this is not rooted at 1). Well, this is a little complicated to explain. I will try my best.

We need to do another dfs (call this dfs_down). The idea here is to have something like

`dfs_down(int node, int parent, pair<int, int> farthest_leaf_from_up)`

farthest_leaf_from_up is {leaf, distance}So lets see how can we calculate for a child of

node(so we want an array of tuples called`diam_down`

similar to above), the diameter on the subtree of the child which is not rooted at 1 (What I mean is the resulting subtree that containsnodeif we take the child and cut the edge fromnodeto the child. What are the possibilities? Well again, we have 2 cases. The first option, the diameter is in other child ofnode(different to the one we are cutting) (note that in this case, the parent ofnodeis also a child) or it crosses thenodeso we need the 2 maximum of children ofnode(but different of the child we are cutting). So since we are atnode, it means that the answer of the parent of node its already (the diameter of the parent ofnodethat doesn't contain any node ofnodeand also, we have the answer for the children ofnode(this is what we did in dfs_down). So for the first option, we only need to consider the maximum of all of them (excluding the child we are cutting). So basically you need the 2 maximum among children, and if the maximum is the child you are calculating the answer for then take the second maximum or take`diam_down[parent]`

, the maximum among them. Now for second (when it crosses) since we have farthest_leaf_from_up that is the farthest leaf from node u to some node in the up subtree ofnodewe can do similar, take 2 maximum that doesn't go for the child we are calculating for. and update the answer, and then call dfs for each children sending the correct value of`farthest_leaf_from_up`

.Now, since we have calculated for each node diam_down and diam_up, it's easy to answer each query.

I called the first dfs_up, since we are like taking information from children and moving up to answer other nodes. And the second, dfs_down, since we are going down, and calculating the answer for each node in the way we are traversing the tree.

This is a little complicated to explain hehe. Hope you got it with patience. If you have any doubt don't hesitate to tell me. I will try to upload some code when I coded this problem which I think uses similar idea.

PDTA: The complexity is O(n)

UPDATE: here is the code for similar problem Note that I sorted on each dfs, so complexity is O(NlogN) though it can be improved by only saving 2-3 maximums.

Hi -osdajigu-, thank you for your detailed answer. I was able to follow your explanation perfectly until you began to explain how to find the diameter of the subtree of v, and then introduced the function dfs_down. I got confused with the definitions of node, parent, farthest_leaf_from_up, I didn't understand which one was v, etc. I think it would be easier to understand with pictures, so I uploaded the following one to frame the conversation:

So if I understand correctly, the first part of your explanation is about how to find the diameter of subtree 1, which I think I understood perfectly. However, I still don't understand how to find the diameter of subtree 2. Would you mind explaining that part again using this picture as reference (or drawing your own picture if you want)?

Thank you very much