KNODES - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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 depth-first traversal and store 3 things for each node:

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

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

  3. 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).

AUTHOR’S, TESTER’S SOLUTIONS:

setter’s solution
tester’s solution

6 Likes
2

can this problem also be solved using LCA?

3 Likes
3

Given the set of K nodes, is there some way to find the two nodes with maximum distance between them?

4

yes. i guess it can be solved using LCA. order will be Klog(n) and as K<=10^6, so it should pass time limit.

make a dfs on the tree and store depth of nodes ( top has 1 depth) . now, for a Query, from K nodes,
take the node which has least depth , if more than 1 nodes then answer is no.
now, start moving nodes with highest depth towards the lowest depth.

if both sets empty: add node to A set.

else if A non-empty: then check of that node if it belongs to set A or not, to check it belongs or not, that just compare the bottom node of A. LCA( bottomnodeofA, node) == node, then node belongs to A set and add to set A. else not.

if node has not been added yet: check if B is empty, if yes , just add it to set B, else check the same way as we did for SET A.

if still has not added : then it means there does not exist any such path.

Order will be K*log(N) as we are checking LCA for each of K node.

5

It’s solvable with central decomposition tree with O(K log N) complexity.

6

K*log(N) solution is not passing.

7

can anyone point out flaw in this:
1)sort the k nodes by their depth. Keep track of left and right end of the final path(initially,first 2 vertices are the left and right ends).

2)If answer is Yes,current node will always be the child of left end or right end, since nodes are sorted by depth.

3)So i check if current node has left or right end as ancestor. If no, ans is no,else update left or right end then check next node.

1 Like
8

“first 2 vertices are the left and right ends” is wrong. It could turn out that the second node is the parent of the first node.

9

may be with little optimization, it wil pass

10

no they are sorted by depth so second can’t be the parent of first

11

Answer to the question by @fauzdar65:
Try running it on this test:
6
1 2
2 3
3 4
3 5
5 6
1
5
1 2 3 4 6

The answer should be “No”.

Here’s another test:
6
1 2
1 3
2 4
3 5
5 6
1
3
2 4 6

The answer should be “Yes”.

2 Likes
12

thanks… it was failing for these cases when the current path doesn’t include root… however with some modification got AC now …

13

Alternative solution:

Find Leftmost deepest node (say L) and rightmost deepest node (say R).
This can be easily done in O(K) :

  1. R is the node having maximum value of DFS StartTime amongst all the K nodes.
  2. Finding L is not exactly same as finding minimum because there is an edge case of two nodes lying on the same path to the root which needs to be handled differently. Approach:
    1. Initialize L = Input[0].
    2. For-each ‘node’ in Input:
    3. IF L and ‘node’ lie on the same path to the root, then make L=‘node’ iff ‘node’ lies below L.
    4. Otherwise make L=‘node’ iff DFS StartTime of ‘node’ is less than DFS StartTime of L.

Now any node should be lie in the path of L -> LCA(L,R) OR R->LCA(L,R).

Code: https://www.codechef.com/viewsolution/7511572

2 Likes
14

how did you get the values of ‘L’ and ‘R’?

15

@admin
if we do dfs and keep track of the connecting components like all nodes vs their group no(connected).
then for each query we just need to go that positions and check whether all contain the same group no or not.

16

Updated the description.

17

Can’t figure out why the sunmission is going wrong . Tried amost every test case .
Plz help …!
Submission
link

18

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.

2 Likes
19

Can anbody give me a test case where my code is failing

link to code: https://www.codechef.com/viewsolution/20359765

20

Can anbody give me a test case where my code is failing

link to code: https://www.codechef.com/viewsolution/20359765