First, you probably mean a/2^k where a,k are integers, not a/2.
There are many unanswered questions here.
How would you store a1, a2? Computers don’t work with formulas, they work with numbers - beyond a ‘simple’ formula like a1*2^(k2-k1)+a2, millions of calculations could be hidden if not handled properly.
How large can a1 and a2 get (in number of 1-bits, number of bits without leading zeroes in total etc.)? The tighter the bounds, the better.
Is ANDing numbers really a good idea? It’s O(k). When k gets large (e.g. for a long stalk with alternating colours), we get O(N^2). If you just do 1<<(p-1) as k +=p-1, then this solution’s complexity is catastrophic.
Ok, enough flame for now. What I would’ve done (and did) better:
You might be familiar with the trick ‘BIT over HLD’, using which you can answer queries on trees online quickly. What I used is: bigint over HLD.
My bigint separately stores the integral and positive fractional part. The advantage of positive fractions is that adding them is much simpler than if you had to think about signs. And what I really need for deciding the number p by which I shift is just the integer in front of it. The fractional part is stored as a map<> of (bit,value) and an integer exp, which means that the fraction’s a sum of terms ‘value*2^(bit+exp)’. Let’s denote a number for which all ‘value’-s in the map are 1-s as standard.
Adding number B into number A (with both fractional parts in standard forms) works this way: add the integral part of B to that of A (duh), then add all entries (bit,value) of B into A as (bit+B.exp-A.exp,value). When you add anything into the map<>, convert it into standard form immediately - start with the entry with the key b=bit+B.exp-A.exp, and while for (b,value) we have value > 1, add (b+1,value/2), set value := value%2; in case value is 0, delete it from the map<>; move to b+1. This works because there’s always at most 1 key whose value is non-1, and that’s the key b.
It’s still possible that the integral part could get larger - and if we have the normal form, then we know that for every (bit,1) with bit >= 0, we can remove it from the map<> and add 2^bit to the integer.
Notice that adding integers is trivial.
What about shifting by a? It’s clear that for the fractional part, it’s just exp -=a. The integral part needs a bit (no pun intended) more care. We can afford to simply shift by 1, a times; each such shift is about subtracting INT%2 (integral part mod 2, non-negative modulo) from INT and if INT was odd, adding it to the fractional part in the same way as described before; then INT /=2. Note that this way, we can ensure that the result is really the number we wanted to get, with the fraction still in standard form.
We’re now able to do both required operations. Another useful one is checking whether the current number is integer, but that’s just checking if the map<>'s empty. The really powerful trick is in not copying all numbers from sons of vertex R into R when computing the comb. game value of R’s subtree, but copying all but one of them into the value of that one son and remembering just where the result for R really is.
If we pick the son which had the largest subtree, we can ensure that any bit is added at most O(log N) times this way. Plus, any bit can only be subtracted at most once, there are at most O(N) bits in total (they come from the numbers p mentioned in this editorial, but p can only be larger than 1 by about as much as the number of times p was equal to 1 when processing the subtree) and therefore there are at most O(N) right shifts, and the integral parts can (for the same reason) only be up to O(N), so they only have O(N log N) bits in total. The resulting complexity is then O(N log^2 N); the other logarithm comes from the complexity of array operations.
Hope this was useful.