Subtask 1

A brute-force solution would be sufficient.

Time Complexity: ~\mathcal O(N^2)~

Full Solution

Let's first consider the following array:

0 2 0 0 0 0 0

If we take the prefix XOR of the array, we will obtain the following:

0 2 2 2 2 2 2

If we take the prefix XOR again we will obtain the following:

0 2 0 2 0 2 0

We can apply this technique to increment every other node for multiple segments in the array in ~\mathcal O(N)~ time using a similar technique as prefix-difference array.

Using the observation above, we can easily apply it on a tree using LCA.

The implementation is left for readers as an exercise.

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