I have recently learned centroid decomposition and want to solve this question. I’ve read the editorial but didn’t get the real idea explained there. Though after reading that I came up with a solution :
I thought of storing all the values of distances (in original tree) of all the node in the subtree of a root(in decomposed tree) and whenever update comes then we can binary search for the reduced ‘k’ (k remained after coming to this root (i.e. k - dist(v, currentRoot)) and then simply add the value (a, b) at that index and at the time of query we can again search for the reduced index (i.e. dist(v, currentRoot)) and get the sum of (a, b) from that upto the last index(as dist(v, root) denotes that this much distance we need if any node gave the contribution to out queried node. so, all the values greater than that value will contribute to our answer.) and then just find the dist(v, root)th fibonacci number and add that to the answer. (repeating this for all the logN ancestors)
Now, one thing remains to do is while querying for a root we must erase the contribution of the branch from which we come to that root! so, for that again at the time of updating we can maintain simultaneously another segment tree for each individual branch and then remove the contribution from that tree.
But time limit of this is very strict and I think instead of being O(log^2N) it won’t pass because of many overheads and also when i’m implementing this solution I faced difficulty in the second part (maintaining another tree for each branch).
So, I want to understand the editorialist approach. So, if someone can explain the update part it will be helpful for me.
Thanks in advance !