PROBLEM LINK:Author: Devendra Agarwal 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:
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). AUTHOR'S, TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 30 Jun '15, 16:03

Answer to the question by @fauzdar65: The answer should be "No". Here's another test: The answer should be "Yes". answered 20 Jul '15, 01:34
thanks.. it was failing for these cases when the current path doesn't include root.. however with some modification got AC now ..
(20 Jul '15, 02:07)

Here is another approach (source): pick first and last vertex of path (start and finish); now for every vertex it lies on the path if and only if dist(v,start)+dist(v,finish)=dist(start,finish). You may find every distance in log(N) time using LCA. answered 25 Jul '15, 02:57

Given the set of K nodes, is there some way to find the two nodes with maximum distance between them? answered 20 Jul '15, 00:31

Can anbody give me a test case where my code is failing link to code: https://www.codechef.com/viewsolution/20359765 answered 28 Sep '18, 16:55

Can anbody give me a test case where my code is failing link to code: https://www.codechef.com/viewsolution/20359765 answered 28 Sep '18, 16:56

can this problem also be solved using LCA?