## Editorial for COCI '15 Contest 4 #5 Galaksija

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Let us choose an arbitrary node to be the root of some tree. Let us denote with the total XOR of all the curiosities on the path from node to node . It can be easily seen that a pair of planets is boring if and only if it holds .

Let us notice that we can "reverse" the input data so, instead of destroying the paths, we can add them.

For connecting the components we will use the union-find algorithm where we will, for each component, remember its root, size and, additionally, a hash map that remembers the number of times appears in the component.

When we need to connect two components, the newly created component is rooted in the root of the larger component. Now we must traverse the entire smaller component (e.g. using the DFS algorithm) and correct the values in the larger component's hash map.

The time complexity of this algorithm is .

## Comments