クエリを \(B\) 個ずつに分割して処理することを考えます。

\(B\) 個のクエリに登場する頂点はたかだか \(B\) 種です。ここに頂点 \(1\) を加えた頂点集合に対し、いわゆる Auxiliary Tree を構築します。(参考: https://atcoder.jp/contests/abc340/editorial/9249)

\(B\) 個のクエリに関係しない頂点の \(A\) の値はこれらを処理する間は固定であるとして良いです。

このとき、 Auxiliary Tree の各頂点 \(v\) において、 Auxiliary Tree においての子の集合を \(C'(v)\) とすれば、ある定数 \(a_{c'}, b_{c'}, c_v\) が存在し、 \(\displaystyle f(v)=A_v+c_v\times\prod_{c'\in C'(v)}(a_{c'} \times f(c') + b_{c'})\) と表されます。 \(a, b, c\) は適切な木 DP により \(\Theta(N)\) で計算できます。詳しくは実装例を参照してください。

また、各クエリごとに、Auxiliary Tree の各頂点 \(v\) に対し \(f(v)\) を求め直します。前述の \(a,b,c\) を用いることで、これは \(\Theta(B)\) で可能です。

よって \(\Theta(NQ/B + QB)\) の計算量でこの問題を解くことができ、 \(B=\sqrt N\) とすれば \(\Theta(\sqrt N Q)\) で、十分高速です。

実装例 (C++, 3232 ms)