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

タイプ \(2\) のアクションが \(u = v\) のものしか与えられないとします。

このとき、頂点 \(1\) を根として考え、以下の要素を更新することを考えます。ここで、\(pare_{i}\) は頂点 \(i\) の親頂点の番号とします。

• \(f(x) = \sum_{r = 1}^{N} W_{r} d(r, 1)\) と定義したとき、
  • \(f(1)\)
  • \(f(i) - f(pare_{i})\)

タイプ \(1\) のクエリが来た際、\(f(1)\) の値は \(O(1)\) で更新できます。

\(f(i) - f(pare_{i})\) については、頂点 \(1\) と \(v\) の(端点を含まない)パス上の頂点 \(i\) ついては \(w\) 減り、そうでない頂点は \(w\) 増えます。

よって、\(f(i) - f(pare_{i})\) を管理する配列を HLD 分解した順番で遅延セグメントツリーを用いて管理することで、高々 \(O(\log(N))\) 回の区間加算クエリに帰着できるので、時間計算量 \(O(\log^{2}(N))\) で更新することができます。

タイプ \(2\) の行動であって、\(u = v\) であるものについては、上記のように更新された遅延セグメントツリーの区間和クエリになり、HLD 分解されていることから高々 \(O(\log(N))\) 回の区間和クエリを処理すればいいので、クエリごとに時間計算量 \(O(\log^{2}(N))\) で処理できます。

\(u = 1\) であっても、遅延セグメントで管理するものに、要素数と累積和の和を加えることで答えを求めることができます。

これらを用いて、一般のタイプ \(2\) のクエリに処理することができます。

c++ による実装例 1175ms