Basic Trees, Path, DFS would do the trick.Understanding of Euler tree tour or Binary Lifting would be helpful.
Given a tree and location of Tarini X, find if shop P lies in path of Taran T and X.
Root the tree on $X$ and just check whether Node $T$ lies in subtree of node $P$ using euler tree tour.
Root the tree on $X$ and check if $P$ is an ancestor of $T$ using binary Lifting.
Since we have a node given, rooting the tree can significantly reduce complexity of our solution.
Suppose we have rooted the tree at some node other than X. Let LCA of X and T be L, then our problem is to find whether P lies on path X to L or P lies on path L to T. If either is positive, answer is true.
Just by rooting the tree at X, we reduced above problem to checking if P lies on path of X to T as LCA (root,T) is root.
Euler Tour Tree Solution
Euler tour can be defined as the tour of tree in a DFS manner, so as to flatten the tree into an array.
The notable properties of this ordering is that,
- Each vertex is visited exactly twice, one time during entering, and once during leaving.
- Each vertex has a corresponding interval, ranging between entry time ans exit time.
- **Node X is in subtree of node Y if Node Y is entered before Node X and X is left before Node Y. Formally, if st denote start time and en denote end time, then node X is chid of Node Y is st[Y]<= st[X] and en[X] <= en[Y].
This is all we need to solve this problem using euler tour. Just run a dfs to compute st and en array, thus answering subtree queryies in O(1).
Binary Lifting Solution
We now view the problem in a different manner. Root the tree at X and we need to check if node P is an ancestor of node X.
This a standard binary lifting problem and can be solved as explained by following cases, D[X] denote depth of Node X.
- If D[P] >D[T] ans is NO.
- Else Find ancestor of Node T at same depth as P. If P is that ancestor, answer is YES, else answer is NO.
Solve same problem, but X varies with each query.
Euler Tour solution: Precomputation O(N), O(1) per query.
Binary Lifting soluton: Precomputation O(N), O(logN) per query.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to share your solution or ask any doubts.
PS:There doesn’t exist any person called Tarini, except in mind of Setter.