Bitwise Tree — An interesting Problem

Revision en5, by dewansarthak1601, 2022-08-10 19:55:37

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

Tags trees, binary tree, lca, graphs, binary lifting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English dewansarthak1601 2022-08-10 19:55:37 124
en4 English dewansarthak1601 2022-08-10 19:52:27 103 Tiny change: 'br>\nn = 3\ntree_fro' -> 'br>\nn = 3 <br>\ntree_fro'
en3 English dewansarthak1601 2022-08-10 19:51:02 496
en2 English dewansarthak1601 2022-08-10 19:43:32 4 Tiny change: 'integers (_say, u and v_). For eac' -> 'integers (say, u and v). For eac'
en1 English dewansarthak1601 2022-08-10 19:43:06 517 Initial revision (published)