dewansarthak1601's blog

By dewansarthak1601, history, 7 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dewansarthak1601 (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dewansarthak1601 (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dewansarthak1601 (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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);

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but using normal LCA for all queries will give TLE seeing the constraints,right?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it