 # CSPT06 - EDITORIAL

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

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.

1 Like