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.