Help needed in a tree problem

1

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 :sweat_smile:
So please help me with it. :slightly_smiling_face:

Code : Submission (44684324) for XYZ Path queries | HackerEarth

2

Actually, I am finding difficult to understand your code. But I also used to same logic to solve this question. Mine got accepted in first try. I think after looking this, you will understand.

3

Thanks for responding.
Actually i want to know where did i messed up. :sweat_smile:
I tried to explain my approach properly.
It 'll be really kind of u, if u can help me in improving my approach
You can ask me whichever part wasn’t clear :slightly_smiling_face: