PROBLEM LINK:
Author: Devendra Agarwal
Tester: Surya Kiran
Editorialist: Amit Pandey
DIFFICULTY:
Medium
PREREQUISITES:
DFS
PROBLEM:
You are given a tree. You need to process Q queries. Each query gives you K nodes and you need to print “Yes” if there is a path connecting them, and “No” otherwise.
Quick Explanation:
We will try building a path to solve this problem. A path will have 2 end points and we will first try to find out these two end points (say D and RD) and then try to check if all the nodes lie either on the path from D to the root or from RD to root.
Now, if the above conditions are satisfied, we need to check whether they still form a pair or not. Solution contains a detailed explanation of the approach.
Solution:
Fix any node as root of the tree.
Then do a depthfirst traversal and store 3 things for each node:

Depth of the node : It is the distance of the node from the root.

Start time of the dfs : It is the time when the dfs started on the node.

End time of the dfs : It is the time when the dfs ended on the node.
You can increase time by 1 when moving to an unvisited node.
Now for all the given K nodes, find the deepest node and the node closest to root.
Let the deepest node be D and let the node closest to root be S.
We will now partition the set of K nodes into two disjoint sets \mathbf{A} and \mathbf{B}.
Set \mathbf{A} will contain nodes which are on the path from root to D.
Set B will contain the remaining nodes.
How to make set \mathbf{A}?
If the start time of node X is before the start time of node D and the end time of node X is after the end time of node D then node X belongs to set \mathbf{A}. [Using properties of DFS]
If set \mathbf{B} was a null set, then our answer is “Yes”.
Find the deepest node in the set \mathbf{B}, let us name it as RD. [Deepest node in the remaining nodes/set \mathbf{B}]
Now again follow the same procedure to partition the set \mathbf{B} into \mathbf{C} and \mathbf{E} where set \mathbf{C} contains nodes from set \mathbf{B} which are on the path from RD to root of the tree.
If set \mathbf{E} is not empty, then our answer is “No”. ( Reasons ? : I hope the readers to use pen and paper to draw a diagram and understand how things are moving, from there it will be trivial to find the reason)
Now, Find the LCA of D and RD. Let us call this node as L.
L must lie between S (smallest depth node in K nodes) and root of the tree for a valid path to exists.
Reason:
If S lies in between root and L, then there does not exist any path.
L must be repeated twice in the journey from D to RD. Hence not a path.
Time complexity of this algorithm is \mathcal{O}(N) (for dfs part per test case) + \mathcal{O}(K+log(N)) (per query).