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 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.