CareerCup

We are given a undirected tree with N (1 to N) nodes rooted at node 1. Every node has a value assigned with it, represented by array - A[i] where i:[1:N].

We need to answer Q queries of type : -> V X : longest length of the common prefix between V and any ancestor of X including X, in their binary representation of 62-bit length.

Common prefix between 2 numbers is defined as:

Example :

4: 0..................0100 (62-bit binary representation)
6: 0..................0110
Considering both as 62-bit in it's binary representation.
Longest length of the common prefix is: 60 (as 60 left most bits are same.)
Now we are given the N (num nodes), edges, nodes values (A[i]) and queries, and we need to answer each query in optimal time.

Constrains :

N <= 10^5, number of nodes
A[i] <= 10^9, value of each node
Q <= 10^5 ,number of queries
Edge[i] = (i, j) <= N
Approach :

Create tree and track the immediate parent of each node.
for Each Query : [V, X], traverse each node n(in the path from X to root) and XOR each node's values with V and find the most significant set bit for each of the XOR operation and pick the minimum one among all of them.
So the result for Query : [V, X] : 62 - (1 + Step-2 result).
Is there any other efficient way to solve this problem? As the above approach in worst case takes O(n^2) time.