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](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!
↵
Source problem: [https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=728&page=show_problem&problem=5691](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!
