Observations

First, let's analyze the relation ~s_i = s_{p_i} \oplus s_{p_{p_i}}~. You may notice how it is very similar to the recurrence in the well known Fibonacci Sequence, where ~F_n = F_{n-1} + F_{n-2}~.

There are two properties of the bitwise XOR operator that are helpful here:

• ~x \oplus x = 0~
• ~x \oplus 0 = 0 \oplus x = x~

If we consider a single XOR Fibonacci Sequence:

~x, y, x \oplus y, y \oplus x \oplus y, x \oplus y \oplus y \oplus x \oplus y...~

Based off of the two properties above, we can see that the sequence repeats every 3 terms:

~x, y, x \oplus y, x, y, x \oplus y...~

Therefore, for every modify operation, if we let ~dist(i, u)~ be the number of edges in the simple path from node ~i~ to node ~u~, the value of ~s_i~ depends on ~dist(i, u) \mod{3}~.

Subtask 1

In this subtask, ~u=1~ for all modify operations, so we only need to consider one rooted tree.

Notice how nodes with the same ~dist(i, 1) \mod{3}~ will have the same ~s_i~ and ~c_i~. Let ~val_m~ be the value of ~c_i~ of nodes ~i~ with ~dist(i, 1) \equiv m \pmod{3}~.

For each modify operation, we can update the following:

• ~val_0 \leftarrow val_0 + y~
• ~val_1 \leftarrow val_1 + (x \oplus y)~
• ~val_2 \leftarrow val_2 + x~

For each query operation, the value of ~c_v~ is simply ~val_{dist(v, 1) \mod{3}}~.

Time Complexity: ~\mathcal{O}(N + Q)~.

Subtask 2

For the full solution, we need to be able to efficiently do the following for modify operations:

• ~c_i \leftarrow c_i + y~ for all ~i~ such that ~dist(i, u) \equiv 0 \pmod {3}~
• ~c_i \leftarrow c_i + (x \oplus y)~ for all ~i~ such that ~dist(i, u) \equiv 1 \pmod {3}~
• ~c_i \leftarrow c_i + x~ for all ~i~ such that ~dist(i, u) \equiv 2 \pmod {3}~

Without loss of generality, let's only consider the first task (the remaining two can be done in similar ways).

We can do this by building a centroid tree ~C~ of the original tree ~T~. One useful property of a centroid tree is that for any two nodes ~a~ and ~b~, the lowest common ancestor of ~a~ and ~b~ in ~C~ will always lie on the simple path of ~a~ and ~b~ in ~T~. Therefore, the set of nodes that we need to update are ~\{a |dist(u, LCA(u, a)) + dist(a, LCA(u, a)) \equiv 0 \pmod {3} \}~, where ~LCA~ is the lowest common ancestor of the two nodes in ~C~ (Note: ~dist~ is still referring to the original tree ~T~).

To update, we can iterate all ancestors ~a~ of ~u~ in ~C~ (including ~a = u~) and make a note to update all ~c_b \leftarrow c_b + y~ such that ~b~ is a descendant of ~a~ in ~C~ and ~dist(u, a)+dist(b, a) \equiv 0 \pmod{3}~. However, just doing this is incorrect, since when ~a \not= u~, we must also ensure that ~LCA(u, b) = a~. To do this, notice how some descendants of ~a_{prev}~ (the previous ancestor that we considered) would have ~a_{prev}~ as their lowest common ancestor with ~u~. Therefore, we need to make an additional note to do ~c_b \leftarrow c_b - y~ (revert the update), such that ~b~ is a descendant of ~a_{prev}~ and ~dist(u, a) + dist(b, a) \equiv 0 \pmod{3}~.

For query operations, we can calculate ~c_v~ by iterating all ancestors of ~v~ (including itself), and updating ~c_v~ based on the notes we made in previous modify operations.

Building the centroid tree can be done in ~\mathcal{O}(N \log N)~ through centroid decomposition, and because the height of a centroid tree is ~\mathcal{O}(\log N)~, each operation can be done in ~\mathcal{O}(\log N)~.

Time Complexity: ~\mathcal{O}((N+Q) \log N)~.