この問題は様々な解法があるようです。一例として、重軽分解 (HLD) を上手に応用した解法が生成 AI によって指摘されています。 また、top tree を利用した解法もあります。
この解説では Static top tree を利用した解法を説明します。

Static top tree の詳しい解説は ABC351-G 公式解説 に譲るとして、ここでは Static top tree の意義について説明していきます。

Static top tree の中身を簡単に言うと、「木をセグメント木みたいに分解したもの」です。少し詳しく言うと、「木を分解する過程を表した深さ \(\mathrm{O}(\log N)\) の二分木」です。
木と Static top tree の関係は列とセグメント木の関係に近いので、まずは列とセグメント木の関係を振り返ってみます。
任意の列 \(a\) に対して、その列のある情報 \(F(a)\) に注目したい場面を考えます。(簡単な例だと \(\max\) など。すなわち、数列 \(a=(1,2,4)\) に対して \(F(a) = \max(a) = 4\) に注目したいとする。) このような場面におけるアルゴリズムを構成する時に、「列を 1 要素になるまで半分に分割する過程を表した深さ \(\log |a|\) の二分木」(\(\simeq\) セグメント木) を考えることが有用です。直接的な例を考えるだけでも、

• 数列 \(a\) の要素を 1 点更新した時の \(F(a)\) の再計算 (セグメント木の 1 点更新)
• セグメント木の区間取得クエリや区間更新クエリをはじめとする、部分列に関する情報の取得・更新
• \(F(a)\) の計算に空間計算量 \(\mathrm{O}(|a|)\) かかる場合の、列全体の情報の高速計算 (いわゆる列のマージテク)
  \(\vdots\)

などが挙げられて、merge sort tree などの応用例も含めると枚挙にいとまがありません。セグメント木は列に関する情報を処理するための汎用的な列の分解手法であると言えるでしょう。

木で同じような概念を考えた時に、列に対するセグメント木に当たるものがまさに Static top tree になります。
任意の木 \(T\) に対して、その木のある情報 \(F(T)\) に注目したいとします(\(F(T)\) の例：最大重み独立集合の重み) この時、列の場合と同様に「木を分解する過程を表した深さ \(\mathrm{O}(\log N)\) の二分木」を考えることで、例えば

• \(T\) の要素を 1 点更新した時の \(F(T)\) の再計算
• 部分木に関する情報の取得・更新
• \(F(T)\) の計算に空間計算量 \(\mathrm{O}(T の頂点数)\) かかる場合の、木全体の情報の高速計算
  \(\vdots\)

などに対応することが出来ます。言い換えると、列の上でできた様々なアルゴリズムが、Static top tree を介することで木の上でも適用可能になります。

Static top tree は 2021 年に noshi91 氏が Twitter (現 X) 上で言及したのが初出だと考えられます。このように競技プログラミングの歴史の中でも比較的新しい手法でありながら、適用範囲の広汎さや使いやすさから、2026 年現在では日本人最上位層に広く知られる手法になりました。

実際に Static top tree の威力を理解するためにまずは 1 個前の F 問題を見てみましょう。想定解は賢い考察を利用して解いていますが、この問題は「頂点 1 点更新 / 木 DP 結果取得」とみなすことができるので Static top tree を持ち出すと直ちに解くことが出来ます。(木 DP は部分木 \(U\) に関する情報 \(F(U)\) を計算するアルゴリズムなので、前述した「木に関する情報を知りたい」というシチュエーションに合致します。) 具体的な適用方法については ABC351-G 公式解説 をお読みください。 実装例

G 問題も Static top tree を利用して解くことを考えましょう。G 問題は「頂点 1 点更新 / 任意の頂点を根とした時の 木 DP 結果取得」と考えることが出来ます。つまり、全方位木 DP(rerooting DP) の結果を動的に更新するアルゴリズムが求められています。これもまた Static top tree で処理可能ですが、 ABC351-G 解説では詳しく触れていないので簡単に説明します。
(以降の説明は ABC351-G 解説の知識を前提とします。) rerooting DP は通常の DP に比べて難解であるため、Static top tree 上の rerooting も難解になりそうに思えますが、原理自体はそこまで難しくないです。DP の根を \(v\) とします。木から 頂点 \(v\) を取り除いた時の、残りの各連結成分に関する DP の情報がわかれば頂点 \(v\) を根とする DP の結果がわかります。ここで Static top tree の性質上、残りの連結成分たちの情報は \(\mathrm{O}(\log N)\) 個の cluster にまとまっていることがわかります。よって、各 cluster に載せた情報を適切に管理・更新することにすれば通常の木 DP と同様に更新と取得を \(\mathrm{O}(\log N)\) で行うことが出来ます。
ただし、通常の木 DP の動的化では path cluster をマージしていく際に「上向き, すなわち根に近い boundary vertex 側に DP の根があるとした時の DP の値」のみを保持すればよかったのに対して、rerooting DP では「下向き, すなわち葉に近い boundary vertex 側に DP の根があるとした時の DP の値」を保持する必要が出てきます。これに伴い実装もいくらか複雑になる点に注意してください。

計算量は \(\mathrm{O}(N + Q \log N)\) で十分高速です。