JTREE- Unofficial Editorial

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 :slight_smile:

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?
Thanks.

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.

thank you :slight_smile: