How to solve CHEFTRE

I think the problem setters are busy with upcoming contest hence the editorials are late.

Can anyone help me understand solution for CHEFTRE

I know we have to use HLD and segment tree. But what are we suppose to store in a node of segment tree?

Well, my approach was to store paths of hld in persistent implicit treaps, in each treap node storing straight and reversed hash of its subtree(needed to compare paths in queiries).

So, when u have to do smth with path from a to b u merge the full path from hld paths(this wont mess up anything cause we use persistent treap), then do w/e u want with it, then paste it back or somewhere else.

For some reason it takes like 1.4k Mb of memory(i actually dunno why, probably f*uсked up somewhere with deletion).

P.S. Sorry for bad englando.

P.P.S. I am quite curios about any other solution, but i’m almost sure it exists.

1 Like

u may find it in anudeep editorial;0