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.

Hello, Codeforces!!


Guys, how do you stress-test your solutions? I know at least three possible ways to do it.

1)Right in your solution file
Write second stress-solution ( definitly correct, but quite slow ), generator, checker, ect. right in your solution file as functions and call functions from main.
I personally use this variant, it is fast and convinient. But there is one problem using this method.. When you have your solution fixed, you have to comment all your stress-code.. I have a trick: just make copy of your file before adding stress-testing functions and add them in your second file, after debugging you will have to just fix jour solution in the first file.

2)Python script
Some people write Python scripts to stress their solutions. You have two programs: solution with bug and stress-solution. So you can just generate tests, lauch your solutions, check answers, etc. from Python script.

3)Bash or maybe Bat scripts
Method is idiologically similar to the 2)Python script, but you write bash/bat scripts.


Which method do you use? Or maybe you have your own techniques, share in comments.