Author: Ritik Mittal
Tester: Nitin Gupta
Editorialist: Ritik Mittal




Euler’s Tour, Sqrt Decomposition


Given a tree, for any node x find number all the nodes such that xor sum of the path is zero. You will also have to update some of the edge weights.


The Xor sum of any path from node u to node v can be calculated as the xor sum of the path from node u to root and the path from the root to node v. As the part of the path that will overlap will contribute finally a zero to xor sum.


Using Euler’s tour generate an array that contains XOR sum from the root node to any of the nodes in the tree.

:arrow_right: To calculate query of type one i.e. from a node x all paths of xor 0 :

Get the xor sum value of the path from node x to root, say p, then we need to calculate the frequency of p in the array generated by Euler’s tour.

:arrow_right: For query of type two i.e. to update the value of edge length from u to v :

let the previous value of edge from u to v be p such that u is the parent of v, and to be updated to q. Here all the paths in subtree of v are to be updated, here we need to Xor all of these values by (p^q).

We do all this using sqrt decomposition on the array. See here for code.

1 Like