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

Auto comment: topic has been updated by dewansarthak1601 (previous revision, new revision, compare).Auto comment: topic has been updated by dewansarthak1601 (previous revision, new revision, compare).Auto comment: topic has been updated by dewansarthak1601 (previous revision, new revision, compare).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.

cool

Can you please give the code snippet or some link for log(n) approach of LCA

LCA

If we assign a root node and "push down" edge values to the "to" nodes, we can then use BIT with Euler Tour to process queries based on Node values. If we were asked to do updates, we would have to use a Segment Tree with lazy propagation instead. The total time will be O(n + nlogn + logn).

This problem is a medium intro to Euler Tour with BIT — http://www.usaco.org/index.php?page=viewproblem2&cpid=696.

My solution : https://pastebin.com/L0f26K2E