How can I solve this problem. With a little modification that, the tree is unweighted and every node i is associated with some value A[i]. Now calculate the max(D xor A[i]) , such that i is any node in the path between 2 given nodes u,v. There are as many as 10^5 nodes and 10^5 queries each query contains u, v, and D.
I can solve it by finding the lca = LCA(u,v) and then check for each node between u to lca and v to lca. But the problem is that I have to traverse through every node between u and v. So in worst case if u = leftmost leaf and v = rightmost leaf in the tree. My solution won’t work. How can I solve it more efficiently.