Блог пользователя kashyap2108

Автор kashyap2108, история, 10 лет назад, По-английски

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??

  • Проголосовать: нравится
  • -24
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can u give the problem link?

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Centroid decomposition

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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

»
10 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится +10 Проголосовать: не нравится

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.