kashyap2108's blog

TRee
By kashyap2108, history, 10 years ago, In English

Given a Tree. How to find no.of pairs (i,j) such that XOR of all the paths from I'th node to J'th node is equal to given k??

  • Vote: I like it
  • -24
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can u give the problem link?

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Centroid decomposition

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Check out IOI 2011 Race. It is almost the same, the only difference is that it is about the sum not XOR.

→ Reply
»
10 years ago, hide # |
← Rev. 5  
Vote: I like it +10 Vote: I do not like it

When it's with weighted edges and xor you don't need centroid decomposition. It's much simpler. Consider any vertex as the root of your tree. The compute the xor to every vertex from it. Now get these values (let them be in array called a[]).

Now the problem becomes given a[] and k. Find the number of pairs (i, j) such that a[i] ^ a[j] = k. This can be done easiliy in .

PS: If you didn't get why we can do this reduction to just array consider two vertices U and V and let ther LCA be L. Then the xor of the path will be (weight of path from U to L) ^ (weight of path from V to L) = a[U] ^ a[L] ^ a[V] ^ a[L] = a[U] ^ a[V]. And so we have converted the problem to the problem given above.

→ Reply