説明と実装を簡略化するため、頂点 \(1\) と辺で接続された新たな頂点 \(0\) が存在し、それは色 \(2\) で塗られていると仮定します。 これにより得られるグラフを、頂点 \(0\) を根とする根付き木とみなして、以下この根付き木を考えます。

頂点 \(v \in \{1,\ldots,N\}\) に対して、\(p(v)\) を「頂点 \(v\) の親」として定義します。
頂点 \(v \in \{1,\ldots,N\}\) に対して、\(q(v)\) を以下のように定義します：

• 頂点 \(v\) から色 \(C_v\) の 親 に移動することを \(0\) 回以上繰り返して到達できる頂点のうち、頂点 \(v\) から最も遠いもの。
  • 頂点 \(0\) の定義から、\(q(v) \in \{1,\ldots,N\}\) であり、特に \(p(q(v))\) が定義可能であることに注意してください。

頂点 \(v \in \{0,\ldots,N\}\) と色 \(c \in \{0,1\}\) に対して、\(S_c(v)\) を以下のように定義します：

• 頂点 \(v\) から色 \(c\) の 子 に移動することを \(0\) 回以上繰り返して到達できる頂点 \(u\) にわたる、\(W_u\) の合計。
  • 直感に反するかもしれませんが、\(C_v \ne c\) であっても頂点 \(v\) 自身は常に条件を満たす（\(W_v\) は常に和に加算されている）ように定義されていることに注意してください。

各クエリと \(S_c(v)\) の関係について、以下のことが分かります。

• クエリ \(3\) の答えは \(S_{C_v}(q(v))\) に等しいです。
• クエリ \(2\) は、
  • \(p(q(v)) - v\) パス上の各頂点 \(u\) （両端含む）に対して、\(S_{C_v}(u)\) に \(x\) を足し、
  • \(S_{1 - C_v}(v)\) に \(x\) を足す操作に等しいです。
• クエリ \(1\) は、
  • \(p(q(v)) - p(v)\) パス上の各頂点 \(u\) （両端含む）に対して、\(S_{C_v}(u)\) から \(S_{C_v}(v)\) を引き、
  • \(C_v\) を \(1 - C_v\) に変更し、
  • \(p(q(v)) - p(v)\) パス上の各頂点 \(u\) （両端含む）に対して、\(S_{C_v}(u)\) に \(S_{C_v}(v)\) を足す操作に等しいです。
    • ただし、\(C_v\) の変更により \(q(v)\) の値も変わっている可能性があることに注意してください。

なお、\(W_i\) と \(C_i\) の初期値は、すべての \(c, v\) に対して \(S_c(v) = 0\) から始めて、クエリ 「\(2 \,\, i \,\, W_i\)」 (\(i \in \{1, \ldots, N\}\)) 及び（\(C_i = 1\) なる各 \(i\) に対する）クエリ「\(1 \,\, i\)」 と見なして、同様に処理することで反映できます。

したがって、\(S_c(v)\) は木上の一点取得・区間加算ができれば処理することができ、これは重軽分解と Fenwick Tree の組み合わせによって、クエリあたり \(O(\log^2 N)\) 時間で実現できます。
また、\(C_i\) も同様のデータ構造上で管理することにより、\(q(v)\) を Fenwick Tree 上の二分探索によりクエリあたり \(O(\log^2 N)\) 時間で取得することができます。

以上により、この問題を \(O((N + Q) \log^2 N)\) 時間で解くことができ、これは十分高速です。