Colorful Works

The first move is to stop trying to draw the trees. The tree part looks huge, but modulo $2$ it collapses into a small take-away game. Nice little scam.

Fix only upper bounds $R_i$ for all colors. Let $G_p(R)$ be the parity of the number of possible rooted subtrees when the edge to the parent has color $p$. For the real root, use a fake color $p=0$ that forbids nothing.

At a node, because two incident edges cannot have the same color, for every color $c\ne p$ we may choose either:

• no child by color $c$;
• one child by color $c$, then any valid subtree below it.

So, modulo $2$,

$G_p(R)=\prod_{c\ne p,\ R_c>0}(1+G_c(R-e_c)).$

This means $G_p(R)=1$ iff all legal next states have value $0$. That is exactly the recurrence for losing positions in this game:

• there are piles of sizes $R_i$;
• a move chooses a positive pile and decrements it;
• the chosen pile color cannot equal the previous move color;
• a player with no move loses.

For the starting state, there is no previous color. The starting state is losing exactly when

$\sum_i R_i \text{ is even}\qquad\text{and}\qquad 2\max_i R_i\le \sum_i R_i.$

Why? If some pile has size $M>S-M$, the first player plays that color. Whenever the opponent plays some other color, the first player plays the huge color again. The other colors run out first, so the opponent gets stuck. If no pile is too large and $S$ is odd, the first player removes from a maximum pile, leaving an even balanced state. If the state is even and balanced, the second player can always answer the first player's move by removing a currently too-large pile if one appears, otherwise any legal pile. After each pair of moves the position is balanced again. Eventually all tokens are consumed after an even number of moves, so the player to move first loses.

Therefore, for upper bounds $R$, the parity is just the indicator of an even balanced vector. No trees anymore. The forest has been legally deleted.

Now restore the lower bounds. By inclusion-exclusion over the conditions $\max d(u,i)\ge l_i$, the answer is the xor over endpoint choices

$b_i\in E_i,$

where

$E_i=\begin{cases}\{r_i\},&l_i=0,\\ \{l_i-1,r_i\},&l_i>0.\end{cases}$

For each chosen vector $b$, we add

$[\sum b_i\text{ is even}][2\max b_i\le \sum b_i].$

So we need the parity of endpoint choices with even sum and no strict majority.

Let

$a_i=\begin{cases}r_i,&l_i=0,\\ l_i-1,&l_i>0,\end{cases}$

and let

$B=\sum_i a_i.$

For colors with $l_i>0$, choosing $r_i$ instead of $l_i-1$ adds

$\Delta_i=r_i-l_i+1.$

Define the subset-sum polynomial over $\mathbb F_2$:

$D(x)=\prod_{l_i>0}(1+x^{\Delta_i}).$

A choice has total sum $B+q$, where $q$ is a subset sum represented by $D$.

First count all even-sum choices. If there are no optional colors, this contributes $1$ iff $B$ is even. If there is at least one optional color, the parity is $1$ only in the very specific case where there is exactly one optional color and its $\Delta$ is odd. Everything else gives an even number of even-sum choices.

Now subtract the bad even choices, where one selected endpoint is strictly greater than the sum of all others. Since the total is even, the other side has the same parity as that endpoint, so a strict inequality becomes a same-parity prefix ending two below the threshold.

Let

$P(t)=\bigoplus_{0\le q\le t,\ q\equiv t\pmod 2} [x^q]D(x),$

with $P(t)=0$ for $t<0$.

For a mandatory color $l_i=0$, the endpoint is $r_i$. It is a strict majority iff

$B-r_i+q<r_i,$

so its contribution is

$P(2r_i-2-B).$

For an optional color, write $a=l_i-1$ and $\Delta=r_i-a$. If we excluded this color from $D$, the low endpoint $a$ and high endpoint $r_i$ would seem to need two separate prefix queries. But they combine cleanly:

$D=E(1+x^\Delta).$

The shifted part of $D$ exactly accounts for the low-endpoint case, so the xor of the low and high bad cases is just

$P(a+r_i-2-B)=P(l_i+r_i-3-B).$

That is the key implementation trick. No per-color polynomial division, no nonsense.

We only need coefficients up to $m=\max r_i$. For every query, the index is at most $r_i-2\le m-2$ after subtracting the base outside the chosen color; negative indices simply contribute $0$.

To build $D$, count how many factors $(1+x^k)$ appear. Over $\mathbb F_2$,

$(1+x^k)^2=1+x^{2k}.$

So while scanning $k=1\ldots m$, carry pairs of factors from $k$ to $2k$, and if one factor remains, multiply the bitset polynomial by $(1+x^k)$ using

$f\leftarrow f\oplus(f\ll k).$

Finally convert $f$ into the same-parity prefix array by doing

$f_i\leftarrow f_i\oplus f_{i-2}.$

Then each $P(t)$ query is just one bit lookup.

Complexity per test case is

$O\left(n+\frac{m^2}{w}\right),$

where $w$ is the machine word size used by the bitset. Memory is $O(n+m)$, and the given total bounds are exactly built for this.