Given a tree, find OR of the path between two nodes (u,v).

Please refer this link for the question: https://drive.google.com/file/d/1y1lcx3YrdPO-sbr2rJQYtpkLPQvF-z2A/view?usp=sharing

How to do it using binary lifting? (Please share your code if you're able to do it)

If you really understand the XOR part i dont know why you have an issue with the OR part. Im pretty sure you just use the exact same logic

The XOR of path can be calculated using: Keep xor of every node from the root in xor[] array. xor = xor[u] ^ xor[v] ^ value[lca(u, v)], i guess. Please let me know if I am wrong.

Yes, this method works for XOR but not for OR. What works for OR is the binary lifting you mentioned on the blog. If you know $$$jump[k][i]$$$ being the OR value of going $$$2^k$$$ upwards in the tree starting from $$$i$$$, then you can just calculate the path from both u and v to the lca of them in $$$O(log(n))$$$

Hey, Thanks a lot for the reply. Can you please share the code? I am stuck on this problem, and I am new to binary lifting concept. But this was asked in recent test of mine, so I want to know how to do these type of questions.

Here is a code just for what is related to the binary lifting (i didnt read anything and didnt calculate some stuff):

ImplementationThanks a lot. Really appreciate it.

Imagine root, u, v are on the same path in order.

For the XOR part, cumulativeXOR from u to v is (cumulativeXOR from root to v) ^ (cumulativeXOR from root to u's parent).

For the OR part, I'm guessing that you can store the sum of '1's for each bit from root to each node. So if root, u, v are all on the same path in that order, you can ascertain if a bit is set from u to v by taking sum(root to v) — sum(root to u's parent) and checking if it is > 0. So to get the OR from node a to node b, take the cumulativeOR from LCA(a, b) to a (using the cumulative sum technique I just described), and OR with cumulativeOR LCA(a, b) to b. You can do something similar for XOR.

Hope that I'm correct and hope that this helps.

Here is the solution: https://m.youtube.com/watch?v=ub82Xb1C8os