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 :

1. Create tree and track the immediate parent of each node.
2. 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.
3. 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.

CodePudding user response：

Java: use numberOfLeadingZeros. The classes Long and Integer have a nice set of utility functions.

long commonPrefix(long x, long y) {
    return Long.numberOfLeadingZeros(x ^ y);
}

On any algorithmic improvement: it would not be honest to provide a superb solution here. And it is better you work something out with pen and paper, puzzling the math side. In fact I can see a tiny way. Maybe you can do even better.

CodePudding user response：

Find the length of binary representation of both numbers, if its not the same then there can't be any matching bits, so only leading zeroes are the common prefix. Otherwise we can find the XOR value to find the number of matching prefix bits.

It's a neat trick, because the XOR operation will turn all the matching bits to zero until the left most bit that doesn't match. So, length of the common prefix will be the difference between total length of binary representation of either number(since they're the same length) and the length of the XOR value's binary representation.

Finally, since you want it for 62 bits, you have add leading zeroes, the number of leading zeroes is 62 minus length of either number's binary representation.

So, 62 - length of either number common prefix. Further simplification would mean the answer is 62 - length of xor value;

The only tricky case here if the numbers are same, you can handle that upfront.

int commonPrefix(int x, int y)
    if(x == y)
        return 62;

    int xLength = Math.floor(Math.log(x)   1);
    int yLength = Math.floor(Math.log(x)   1);
    
    if(xLength != yLength)
        return 62 - Math.max(xLength, yLength);

    int xor = x ^ y;
    int xorLength = Math.floor(Math.log(xor)   1);

    return 62 - xorLength;

Once you've got that covered a simple DFS should give you the ancestors of the node you're looking for and you can find the longest common prefix by comparing the given value with every ancestor.