セグメントツリーを用いて \(O(N + Q \log^{2}(N))\) で解くことができます。なお、定数倍は悪いが実装が軽い、同じ計算量の遅延セグメントツリーを用いる解法が存在します。こちらの解説をご覧ください。

タイプ \(2\) は \(u = 1\) のものに限るとします。そうでなくても、\(u = 1\) に限った解を足し引きすることで一般のクエリを処理することができるためです。

頂点 \(1\) を根とした根付き木を考えます。

\(v\) が fix されたタイプ \(2\) のクエリに対する \(W_{r}\) の寄与を考えます。

頂点 \(r\) の深さを \(a\) とし、頂点 \(v\) の深さを \(b\) とし、頂点 \(r\) と最も近い \(1 - v\) 上の頂点の深さを \(c\) としたとき、\(W_{r}\) の答えに対する寄与は以下の式で表せます。

\((a - c)(b + 1) + \frac{c(c + 1)}{2} + \frac{(b - c)(b - c + 1)}{2} = ab + a- \frac{b^2}{2} + \frac{b}{2} - 2bc + c^{2} - c\)

これらの寄与を全て計算すればいいです。

これらを全て説明すると複雑になるので、\(W_{r}c\) の和の求め方のみ説明します。

まず、前処理として HLD をします。

タイプ \(1\) のクエリでは、以下の頂点に \(W_{r} c\) を加算します。ここで、\(c\) は加算する頂点の深さであるとして良いです。

• 頂点 \(r\)
• 頂点 \(r\) と根までのパスまでに存在する軽い辺の、親側の頂点

タイプ \(2\) のクエリでは、頂点 \(1\) から頂点 \(v\) に行くまでに通った頂点を \(1 = x_{0}, \dots, x_{b} = v\) としたとき、\(0\leq i\leq b\) について、以下の値の総和を取ればいいです。

• 頂点 \(x_{i}\) の部分木に含まれているかつ、頂点 \(x_{i + 1}\) の部分木に含まれていない頂点 \(j\) のに対する \(W_{j}\) の総和と \(i\) の積。(ただし、\(i = b\) のときは、頂点 \(x_{i + 1}\) の部分木は空であるとする。)

\(x_{i} - x_{i + 1}\) が重い辺のときは、タイプ \(1\) の処理をするたびにすでに求められており、軽い辺のときは、部分木内の \(W_{j}\) の総和を求めればいいです。

重い辺の処理、部分木内の \(W_{j}\) の総和、どちらも区間和クエリに帰着できます。

よって、セグメントツリーを用いて クエリごとに \(O(\log^{2}(N)\) で処理できます。他の寄与についても同様です。

c++ の実装例 436ms