pabloskimg's blog

By pabloskimg, history, 5 years ago, In English

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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).

»
5 years ago, # |
Rev. 8   Vote: I like it +6 Vote: I do not like it

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 contains node if we take the child and cut the edge from node to the child. What are the possibilities? Well again, we have 2 cases. The first option, the diameter is in other child of node (different to the one we are cutting) (note that in this case, the parent of node is also a child) or it crosses the node so we need the 2 maximum of children of node (but different of the child we are cutting). So since we are at node, it means that the answer of the parent of node its already (the diameter of the parent of node that doesn't contain any node of node and also, we have the answer for the children of node (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 of node we 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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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