Let's jump straight into the problem
Source problem: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=728&page=show_problem&problem=5691 (2016 Beijing ICPC regionals, problem B)
Aim: Support #5, #6, and a cutting operation simultaneously (I have written a piece of code which supports the first four operations)
What I have achieved so far:
Observed that each node's contribution to its parent depends on the amount of right turns taken in the path (Contribution *= -1 per turn)
Use Link Cut Tree to maintain the amount of nodes which have positive/negative contribution to a node (which I call "sign"), and the values of all nodes if there is no subtree updates in the queries, as all these queries could be reduced to updating the sign/value of a node and propagate the effects to the root (which is just a path update between a node and the root, supported by the LCT)
And I am lost with the subtree update operation, my prototyped method was to update keep a lazy marker on the designated node, so that when I do queries on ...
Nodes in this subtree: I query the path from the queried node to the root, and accumulate the markers along the way. The markers from the ancestors represents the total range update performed on this subtree, and multiplying it by the "sign" of this node computes the effects of such updates.
Ancestors: When the update comes, I will fire a range value update from the updated node's parent to the root, with the net contribution on the updated node due to this range update operation. Then, when I query the ancestors, the effect of this range update is already stored in the values without considering the lazy markers. (*)
All others node will not be affected by such update mechanic.
However, I have came to the solution (I am glad to be told wrong) that I cannot support cutting operations with such update method. In particular, the update on ancestors (*) relies on firing an one time update operation on its ancestors based on its current contribution, yet, when a cutting operation occurs in the subtree, the sign of the updated node changes and the net contribution on the updated node due to the range update is modified thus the update operation ought to be fired again, which could mean non-constant amount of re-updates need to be performed to push the updates for each cutting operation.
I am interested in learning alternative ways in dealing with this problem. I tried to keep this blog short to attract more interest, if you find that I should be clarifying about something in more details in this post, please let me know.
Thanks in advance.
Edit: Just got AC on the problem. As many have suggested, Euler Tour related dynamic structures instead is the way to go!
Maybe this paper can be useful for you. But the tree is binary, so maybe exists some simpler observation that allows to solve it without fancy data structures.
Thank you! After scanning through the introduction section I think I could mimic these operations with a Link Cut Tree, I was too tunnel visioned into storing stuff in the parents instead of doing it on the subtree.
Maybe a dynamic BBST(tmw168 suggests persistent avl tree) works. Easiest way of handling queries of type 5 is definitely range updates on preorder traversal. For other queries, you just move O(1) ranges around, which should be possible to handle. You may want to check out https://loj.ac/problem/105 for ideas to maintain an array . I'm not sure how link-cut tree works, but maybe there is a way to find out how the preorder changes by that.
Thanks for pointing that out! I was too focused into the Link Cut Tree without thinking that flatenning the tree into a pre-order traversal could work, that should be sufficient for supporting #5 and dynamic link/cut operations.
Usually when you're dealing with path-related queries on dynamic trees, the data structure to look at is the link-cut tree. When dealing with (sub)tree-related queries, the go-to is the Euler Tour Tree (which is just a fancy word for keeping a BST over the Euler tour of the original tree). In the ETT some circular permutations occur, which have to be handled.
Auto comment: topic has been updated by haleyk100198 (previous revision, new revision, compare).