Using Binary Lifting, i tried to take the contribution of each element in the path of x to y.
And then make combinations using the fact that if all the elements in the pair,triplet … (depending on z) will have a current set bit 0, then that choice will not make any contribution for the current bit.For each query i maintained an array (ans) to store where ans[i] stores no of elements on the path from x to y whose ith bit is set. Using depth and Lca i can find the total nodes on the path .
my idea was to get the total contribution of each bit in my final ans. So after getting the
ans array filled i made valid combinations( valid means where current bit will be one)
say total nodes -> n
for z = 3, total triplets = nC3. invalid ones will be those in which all 3 elements will have current set bit 0, so no of such combinations should be… (n-ans[i]) gives no of elements with current setbit 0, so total invalid combinations will be (n-ans[i])C3.
final contribution of each bit is (total triplets - invalid)*(1<<i).
So this was my approach
i got memory limit exceeded error in most of the test cases, some were accepted and some gave wrong answers. i declared global arrays of max size required, so i thought
MLE is not because of my array size, there is some issue in the code itself.
i can’t figure out where i messed up
So please help me with it.