Okay, I will try to help you. I am writing the process of how I approached this problem from the start. (There might and will be some better approaches than mine, but I will try to explain the thought process involved in mine and it will give you the intuition to solve it further).
See, basically after seeing the constraints the first thing that comes in mind is we have to answer each query in O(logn), or maybe O(1). So we need to precompute some values in order to reach this time complexity.
Now, let us arbitrarily root the given tree to 1. We will precompute the number of intersecting paths between the root node (i.e., 1) and any node of the tree and store them in an ans[] array.
How to calculate it? Quite easy!
First of all, calculate the sizes of subtrees of all the nodes and store them in an array sub[](can be done in one dfs).
Now, we will calculate ans[1] i.e., answer of query (1, 1). How?
Let the sizes of subtrees of its children be a, b, c, d (in sample, sizes of subtrees of nodes 3(1), 2(3), 4(1)). The valid intersecting paths must contain 1 in them. So the path between any node from one of the children’s subtree and another children’s subtree will be a valid intersecting path (read this line again and again). For e.g. in sample, Path between node 3 and 4 will be valid, path between node 3 and any node from node 2’s subtree will also be valid, and path between any node from 2’s subtree to node 4 will also be valid, and paths between 1 and any of the nodes in the tree will be valid.
It is easy to see that except the paths originating from 1, they are the sum of product of pairs of sizes of subtrees of children of 1! Let the sizes of subtrees of children of subtrees of children be a, b, c, d. Therefore,
ans[1] = a*b + b*c + a*c + a*d + b*d + c*d + (a + b + c + d) (paths between 1 and any other node) + 1((1, 1) itself).
The sum of product of pairs can be calculated easily during dfs in O(number of children) for each node. Calculate this value for each node during dfs.
Now, to find the number of paths between 1 and any of the nodes, we have to propagate the answer of a parent to its children to get the required answer.
Suppose, we are calculating answer between node 1 and 2 (i.e., ans[2]).
ans[2] initially has the paths consisting of its children’s subtrees only.
Now to get the paths from its parent’s side (its parent is 1), we have to subtract something from its parent’s ans[] value because it will be having some paths which may have more than 1 nodes common with the path 1 - 2. (for e.g, ans[1] will also contain paths like 2 - 1 - 4, which is not required for ans[2]).
Let s = sum of product of pairs (a, b, c, d) + (a + b + c + d). Now what if we want to remove all pairs of d and d itself, how to do that in O(1)? Just subtract the quantity d*((a + b + c + d) - d) - d!
Therefore, to remove the paths like 2 - 1 - 4, we need to subtract sub[2]*(sub[1]-1-sub[2]) - sub[2] (additional minus 1 for getting sum of subtrees of children of 1).
Hence, ans[2] += ans[1] - sub[2] * (sub[1] - 1 - sub[2]) - sub[2])
Hence, answer between root and any of the nodes can be calculated in this way.
Now, I leave the querying part to figure out on your own as an exercise and if you can’t, I will help you, just reply again here.
(Hint: use the precomputed ans[] values and ans[] of LCA!).
My solution: CodeChef: Practical coding for everyone