We are given a tree with ‘n’ nodes .
(a,b) means a path from node ‘a’ to node ‘b’ of the tree.
We are given multiple queries, with 2 integers ‘x’ and ‘y’ .
For each query,we have to consider all pairs of nodes of the tree,i.e, and check if their paths perfectly intersects with the path (x,y) .
Note:- Two paths perfectly intersect if only one node is common between both the paths.
Example:- Consider a tree with the following edges : -
1 2
1 3
1 4
2 5
2 6
Lets consider the following first query:- [4,5].
Answer : - 6
In the first query, the paths that intersect perfectly with the given path (4,5) are (1,1), (1,3), (2,2), (2,6), (4,4) and (5,5) .
My approach:- Simple brute force, but I’m in a search of much more efficient approach which can handle multiple queries. Can you suggest one?
Note:-Tree can have as many as 1000000 nodes and 1000000 queries !
