Great logic! (y)
Awesome explanation with the images, just give a link in official editorial as different approach to the problem
@arunnsit Great explanation. Thanks for that.
But I had one doubt which I hope you will be able to clear. The complexity you told is O(Nlog(n) + M). What I think is, since log(n) time is spent for each ticket and there are M tickets, it should have been O(N + Mlog(n)).
Correct me if I am wrong.
precisely , yes you are right . i mixed variable M with Q . thanks for the correction
I didn’t understand the calculating the vector V.
what we are doing over here is pushing a node u to the vector V when we haven't discovered the subtree of u and pop it when the whole subtree is discovered .
And what is p in dfs(u,p)? Could you elaborate?
I solved it using heavy light decomposition.
Link to my solution : https://www.codechef.com/viewsolution/11338980
p is parent of u . And discovering means if we have already visited the node or not . I meant that if we havent visited any node in the subtree of u , then u should remain in the vector and once all the subtree nodes are visited , we have to pop u .
I would like to say that this is one of the most well written editorials I have ever seen.
It was really clever to build the segment Tree on the basis of height and not node.
No need for topological sort now.