brainy_fool's blog

By brainy_fool, 2 years ago, In English

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)

  • Vote: I like it
  • +11
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like 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

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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))$$$

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          Implementation
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like 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.