for a given path between node u-v in tree find maximum XOR with any node in that path

Question

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

Any help, what will be an optimal way of performing the queries for a number of times.

Answer 1

It is similar to this question Maximum XOR value faster than just using XOR. But queries on the tree. This solution is offline. For every query answer will be max(getxor(LCA(u, v), u, K), getxor(LCA(u, v), v, K)). Perform dfs. When entering node add it to the trie, when leaving erase. In each node of trie store level of node. Then answering to this query can be a simple walk through this trie. To check whether there is suitable prefix higer or equal level[LCA(u, v)] you should do a binary search over stored array in a node. The algorithm complexity is O(log(n) * log(max_node_val))