흑백 트리

Assign weight $+1$ to each black vertex and weight $-1$ to each white vertex. Then a black-white component is exactly a connected vertex set whose total weight is $0$.

Root the tree at vertex $1$. Every connected vertex set $S$ has a unique vertex closest to the root. Call it the top of $S$.

Let $F_v(x)$ be the generating function of connected vertex sets whose top is $v$. Then,

$F_v(x)=x^{w_v}\prod_c(1+F_c(x))$

The answer is the sum of the constant coefficients of $F_v(x)$ over all vertices $v$.

For $N \le 200000$, merging child polynomials one by one in $O(N^2)$ is not enough. Choose one heavy child $h$ and define $A_v(x)=x^{w_v}{\prod }_{c\mathrm{\ne }}$. Then . Along a heavy path, each vertex is an affine transform . Compose these transforms in a balanced way and use NTT for polynomial multiplication. Store for each interval so that the top DP is and the interval contribution is . This gives an -style solution.