LGSEG - Editorial

For all those who are getting SIGSEV in test 3 , change the dp[][] array to global as it’s size will be around 10^6 x 20 which is around 2 x 10^7.

It’s not that difficult. But it’s a bit unintuitive if you’re unfamiliar with dp. I too was stuck understanding the solution for this problem but now I’m clear with it.
If you want to go ahead, do these 3 things in order.

  1. Watch Erricto’s (Errichto - Codeforces) introduction to Binary Lifting : Binary Lifting (Kth Ancestor of a Tree Node) - YouTube (and solve the problem discussed in video afterwards by writing code yourself (not looking/copying) ).
  2. Watch Erricto’s LCA video and solve the SPOJ and CSES question (in description of video) afterwards similarly : LCA – Lowest Common Ancestor - YouTube.
  3. Watch Geothermal’s (Geothermal - Codeforces) video of this explanation (video timestamped) : July 2021 CodeChef Lunchtime - Solution Explanations - YouTube

If still stuck after doing the 3 steps, reply to my comment. I’ll help you out.

3 Likes

https://www.codechef.com/submit/LGSEG
why i am getting wa please tell

This is the problem link. Put your submission link instead.

i have been trying to upsolve this problem since a day but still getting WA in implementing
could anybody help
my solution : CodeChef: Practical coding for everyone

@cherry0697 I think a chain like structure would be formed but not an N-ary tree.
Correct me if I am wrong .