Trie traversal to maximise XOR in a tree but with a condition Input:I am provided with x and y.

x is a 32 bit non negative integer and y is some node-id of the tree.

So, I built a trie with 32-bit non negative integer values which are the keys associated with each node-id of the tree (DAG). Now, if I am asked to find the a node, whose key XOR x is maximum. This can be easily be done in O(log n) just by traversing the trie. 

Now here is the extra condition:

I want to find the key on the node in the path from root to that node y, for which x XOR (key) is maximum. 
How can we find this out efficiently? Preferably in O(log n).
You can simply use persistent tries.

Let $T[x]$ denote a trie containing all keys in the path from root to $x$, assume $y$ is a child of $x$, $T[y]$ can be constructed in $O(\log U)$ time from $T[x]$, where $U=2^{32}$. This is trivial even if you use normal tries; but the key point is "persistent" data structures enable you to store all $T[\cdot]$ at the same time. As an intuition, notice that when we construct $T[y]$ from $T[x]$, only $O(\log U)$ nodes in $T[x]$ changes.