PROBLEM LINK:
Author: Ritik Mittal
Tester: Nitin Gupta
Editorialist: Ritik Mittal
DIFFICULTY:
MEDIUM-HARD.
PREREQUISITES:
Euler’s Tour, Sqrt Decomposition
PROBLEM:
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.
QUICK EXPLANATION:
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.
EXPLANATION:
Using Euler’s tour generate an array that contains XOR sum from the root node to any of the nodes in the tree.
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.
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.