To simplify explanation and implementation, assume that there is also a vertex \(0\) connected to vertex \(1\) by an edge, and it is painted in color \(2\). Regard the resulting graph as a rooted tree with vertex \(0\) as the root. We will consider this rooted tree.

For a vertex \(v \in \{1,\ldots,N\}\), define \(p(v)\) as the parent of vertex \(v\).
For a vertex \(v \in \{1,\ldots,N\}\), define \(q(v)\) as:

• the furthest vertex from vertex \(v\) among the vertices reachable from vertex \(v\) by repeatedly moving to the parent with color \(C_v\) zero or more times.
  • By definition of vertex \(0\), note that \(q(v) \in \{1,\ldots,N\}\), and in particular \(p(q(v))\) is always well-defined.

For a vertex \(v \in \{0,\ldots,N\}\) and color \(c \in \{0,1\}\), define \(S_c(v)\) as:

• the sum of \(W_u\) over all vertices \(u\) reachable from vertex \(v\) by repeatedly moving to a child with color \(c\) zero or more times.
  • Unintuitive as it may seem, note that vertex \(v\) is always qualified (\(W_v\) always contributes to the sum) by definition, even if \(C_v \ne c\).

The queries relate to \(S_c(v)\) as follows:

• The answer to a type-\(3\) query is \(S_{C_v}(q(v))\).
• A type-\(2\) query is equivalent to:
  • for all vertices \(u\) in the \(p(q(v)) - v\) path (including endpoints), adding \(x\) to \(S_{C_v}(u)\), and
  • adding \(x\) to \(S_{1 - C_v}(v)\).
• A type-\(1\) query is equivalent to:
  • for all vertices \(u\) in the \(p(q(v)) - p(v)\) path (including endpoints), subtracting \(S_{C_v}(v)\) from \(S_{C_v}(u)\),
  • setting \(C_v\) to \(1 - C_v\), and
  • for all vertices \(u\) in the \(p(q(v)) - p(v)\) path (including endpoints), adding \(S_{C_v}(v)\) to \(S_{C_v}(u)\).
    • Note that changing \(C_v\) may change \(q(v)\) too.

Here, the initial values \(W_i\) and \(C_i\) can be took into account by starting from \(S_c(v) = 0\) and regarding them as queries “\(2 \,\, i \,\, W_i\)” (\(i \in \{1, \ldots, N\}\)) and queries “\(1 \,\, i\)” (for \(i\) with \(C_i = 1\)) and processing them similarly.

Hence, \(S_c(v)\) can be maintained by element-wise updates and path-wise addition on a tree, which can be done in \(O(\log^2 N)\) time per query by combining HLD (Heavy-Light Decomposition) and a Fenwick tree.
\(C_i\) can also be managed in the same manner, so that \(q(v)\) can be retrieved by binary searching on a Fenwick tree in \(O(\log^2 N)\) time.

Hence, the problem can be solved in \(O((N + Q) \log^2 N)\) time, which is fast enough.