頂点 \(n\) の light child の集合を \(C'(n)\)とおく。\(C'(n)\) が空集合の場合 \(g_i(x) = x + A_i\) とし、そうでない場合 \(g_i(x) = \displaystyle( \prod_{c \in C'(i)} f(c)) x + A_i\) とする。

このとき \(f(n)\) は頂点 \(n\) から heavy child を葉までたどる列を \(p_1 ( = n), p_2, \dots ,p_k\) としたとき \(g_{p_1}(g_{p_2}( \dots g_{p_k}(0)))\) と計算できる。

行きがけ順に頂点を並び替えると、上の関数合成は Segment Tree の区間積取得でできる。更新クエリへの対応を考える。\(g_i(x)\) の定義から、更新する必要があるのは頂点 \(v\) とそこから祖先へ登っていくときに別の heavy path に移る高々 \(O(\log N)\) 箇所のみである。

更新のときには \(n\) に対して \( \displaystyle \prod_{c \in C'(n)} f(n)\) を高速に計算する必要がある。これは bfs ordering で別の Segment Tree を持つとできる。Segment Tree を持たずに、 \(0\) の個数を保持することでも処理できる。

以上を実装すると、時間計算量 \(O(N + Q \log^2 N)\) で解ける。実装例 (C++)