Recently I tried to solve dynamic update/query problems, like Hackerrank - Subtrees and Paths, IOI 2011 - Dancing Elephants, JOI 2013 - Synchronization, Chef and Graph Queries, Query on a tree VI, etc…
During my studies on them, I’ve got to know that link-cut tree is something like universal key, so I learned it from various sources… it took 2-3 days for the mere understanding of the concept, how-it-works and simple implementation…
But when I returned back to tackle those problems, I just got dumb. Update/Query mechanisms demanded are different between problems. e.g., subtree/path - weight/min/max/summation update, ancestor/descendant/path query…
The simplest idea is lazy propagation, but this increases the time complexity when it comes to fertile parents (in auxiliary tree) which can have many unacknowledged child nodes.
I know how to handle subtree weight update, flipping through delta representation. I could understand them through this resource. I thought it was more elegant solution than lazy propagation, but was MUCH harder to implement. Thinking weight, minimum, and even flipping in delta way drove me crazy… It shows that it takes time for new type of update/query thinking about the delta equations…
Is there any exhaustive resource on query and update mechanisms of link-cut tree? How can you implement new type of queries? Is there key concept needed to understand designing dynamic query problems?