For the given path between node uv in the tree, find the maximum XOR with any node in this path

Question

Given a tree, certain 1<=q<=10^5queries exist . Each request has nodes u, vand K. How to find max(KXOR node)where nodethere is any node lying in the path between node u and v. Where XOR is a bitwise operation XOR.

Any help that would be the best way to execute requests multiple times.

Answer 1

This is similar to this question. Maximum XOR value is faster than just using XOR . But the queries are on the tree. This solution is disabled. For each response to the request will be max(getxor(LCA(u, v), u, K), getxor(LCA(u, v), v, K)). Run dfs. When entering node, add it to trie, leaving erasing. In each node storage node level. Then the answer to this request can be a simple walk on this three. To check if there is a suitable higer or equal prefix level[LCA(u, v)], you should do a binary search on the stored array in node. Algorithm complexityO(log(n) * log(max_node_val))