### dewansarthak1601's blog

By dewansarthak1601, history, 2 months ago, 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 lca, Comments (11)
 » 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] . bit[i][j] = number of nodes from root(1) to node i such that there jth bit is set. bit[j] = (1<
•  » » 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
•  » » » » »
 » 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