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.
- 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) ).
- Watch Erricto’s LCA video and solve the SPOJ and CSES question (in description of video) afterwards similarly : LCA – Lowest Common Ancestor - YouTube.
- 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
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 .