Hello, CodeForces!!

I want to describe you a solution for 1702G2 - Passable Paths (hard version) with using only LA (K-th ancestor). This solution does not use LCA finding algorithm.

Let's start with a DFS from 0-s vertex and calculate depth of every node in our tree. We also have to calculate tin and tout for every vertex (we will need it to check if one vertex is in subtree of another vertex).
Calculate binary ups to find LA in logarithmic time complexity. Description of this algorithm you can find in the Internet. Main Idea: calc binups and if we want to get k-th ancestor, just go for every power of 2.
Now let's process queries. Check editorial for this problem. We can do the same greedy trick with finding two paths in array sorted by depths of vertexes. When we have two paths, we can get two highest vertexes in paths X1 — from first path, X2 — from second path. If X2 is not in the subtree of X1 — answer is YES. Else — let us find second-highest vertex in first path — Y1. If X2 is in the subtree of KthAncestor(Y1, depth[Y1] — depth[X1]-1) — answer is NO. Else answer is YES.

Thanks pavook for help.
Share your solutions for this problem in comments.