Given a Tree of n vertices numbered from 1 to n. Each edge is associated with some weight given by array tree_weight. There are q queries in the form of a 2-D array, queries, where each element consist of two integers (say, u and v). For each query, compute the sum of bitwise XOR, the bitwise AND, and the bitwise OR of the weights of the edges on the path from u->v. Return the answer to each query as an array of integers.
Example-
n = 3
tree_from = [1,3]
tree_to = [2,2]
tree_weight = [2,3]
q = 2
queries = [[1,3],[2,3]]
Edges of the tree in the form (u,v,w) are (1,2,2),(3,2,3)
For query 0, u = 1, v = 3;
XOR of the weights = 2 ^ 3 = 1
AND of the weights = 2 & 3 = 2
OR of the weights = 2 | 3 = 3
Hence the answer to this query is 1 + 2 + 3 = 6
For query 1, u = 2, v = 3;
XOR of the weights = 3
AND of the weights = 3
OR of the weights = 3
Hence the answer to this query is 3 + 3 + 3 = 9
Return the array [6,9].
Constraints —
1 <= n <= 1e5
1 <= q <= 1e5
1 <= tree_weight[i] <= 2^20
This is How we can Proceed make 1 as root node , create a 2D array bit[n+1][21] . bit[i][j] = number of nodes from root(1) to node i such that there jth bit is set. bit[1][j] = (1<<j) & w[1] ? 1 : 0 bit[i][j] = (1<<j) & w[i] ? 1 : 0 ; bit[i][j]+=bit[parent[i]][j]
For Now for Each Query u,v we get lca(u,v) = x and calculate number of set bits on the path from for each bit from 0 to 20 and check it contribution to and , or and xor for(int j=0;j<21;j++) num[j] = bit[u][j]+ bit[v][j] — bit[x][j] + ((1<<j) & w[x] ? 1 : 0);
but using normal LCA for all queries will give TLE seeing the constraints,right?
Time Complexity for this approach will be q*logn*21 so it should run under 1 sec. logn factor is for finding lca and 21 is for all bits.
Can you please give the code snippet or some link for log(n) approach of LCA
LCA
My solution : https://pastebin.com/L0f26K2E