木DP・集約・rerooting

概要

木の一部を計算し終えたとき、残りの計算へ何を渡せばよいだろうか。辺を一本切ると二つの成分に分かれることを使い、片側の情報を短く要約する。一つの根の答えが欲しければ子から親へ集約し、すべての頂点を根にした答えが欲しければ逆向きの情報も共有する。

考え方

辺の片側から何を渡すか

独自の小例として、頂点が r,a,b,cr,a,b,c、辺が r–a,a–b,r–cr\text{–}a,a\text{–}b,r\text{–}c の木を考える。各辺の長さは1とする。rr を根にすると、aa の子が bb、rr のもう一つの子が cc である。木の索引化でも同じ木を使う。

各頂点から全頂点への距離の和を求めたい。辺 r–ar\text{–}a を切ると、aa 側は {a,b}\{a,b\}、rr 側は {r,c}\{r,c\} に分かれる。rr から aa 側のどの頂点へ行くにも、最初にこの辺を通る。そこで aa 側の全頂点を毎回たどる代わりに、頂点数と、受け手から測った距離の和だけを渡す。

辺 u–vu\text{–}v を切った uu 側について、vv へ渡す要約を message(メッセージ)と呼び、m(u→v)=(count,sumDist)m(u\to v)=(\mathrm{count},\mathrm{sumDist}) と書く。countはその側の頂点数、sumDistは受け手 vv からその各頂点への距離の和である。この小例では m(a→r)=(2,1+2)=(2,3)m(a\to r)=(2,1+2)=(2,3)。逆向きの m(r→a)m(r\to a) が表す集合は {r,c}\{r,c\} であり、値が同じ (2,3)(2,3) でも別の側の情報である。

自身の追加と、辺を渡る変換を分ける

一つの頂点へ入るメッセージ同士は、成分ごとの和でまとめられる。空の集合の要約は (0,0)(0,0)。葉 bb では、ここへ自身を加えて (1,0)(1,0) とし、辺を一歩渡すと m(b→a)=(1,1)m(b\to a)=(1,1) になる。

aa では、bb から届いた (1,1)(1,1) へ自身を加えると (2,1)(2,1)。さらに rr へ渡すと、二頂点への距離がそれぞれ1増えるので (2,3)(2,3) になる。一般に、自身を加える前の要約を (C,S)(C,S) とすると、自身の追加、長さ1の辺を渡る変換は順に

(C,S)⟶(C+1,S)⟶(C+1,S+C+1)(C,S)\longrightarrow(C+1,S)\longrightarrow(C+1,S+C+1)

となる。rr の答えを取り出すときは、a,ca,c から届いた (2,3),(1,1)(2,3),(1,1) に自身を加え、(4,4)(4,4) の距離和4を読む。答えを取り出す頂点から、さらに辺を渡る変換は行わない。

隣接する各方向の成分は重ならず、そこへ現在の頂点を一度加えると対象全体になる。また、受け手から片側の各頂点への経路は送信側を必ず通るため、辺長だけ距離を増やせばよい。これが、この要約を合成できる理由である。重み付きの辺長が ww なら、辺を渡る際は頂点数を変えず、距離和へ「頂点数 ×w\times w」を加える。

一つの根か、すべての根か

一つの根や各部分木の答えだけが必要なら、葉から子を先に処理して親へ渡す。rr を根にした小例では、b→ab\to a と c→rc\to r を作り、次に a→ra\to r を作ればよい。この流れで、距離和に限らず「親へ何を渡せば十分か」を学ぶのが根付き木DP・部分木集約である。

全頂点の答えが必要なら、根を変えて同じDFSを繰り返すと頂点数を NN として O(N2)O(N^2) かかる。既にある子側の要約を再利用し、今度は親から子へも渡したい。r→ar\to a を作る際は、aa から来た分を除き、cc からの (1,1)(1,1) と rr 自身だけをまとめて渡す。aa から来た分も含めると、{a,b}\{a,b\} の情報を aa 側へ送り返して重複させてしまう。

このように子から親、次いで親から子の二方向を計算すれば、各頂点で全方向の情報がそろう。小例の距離和は r,a,b,cr,a,b,c の順に 4,4,6,64,4,6,6 となる。各送信先の方向だけを除く合成を効率よく共有する方法は、rerooting・全方位木DPへ進む。距離和なら引き算も使えるが、一般の集約では元に戻す演算があるとは限らない。逆元を必要としないprefix・suffixによる除外は、そこで学ぶ。

成立条件と計算量

まず、片側の詳細を捨てても、受け手の計算に必要な情報が残るかを確かめる。上の距離和では距離の増分が頂点数に比例するため、距離和だけでなく頂点数も必要だった。閉路のあるグラフでは、辺を切った両側が独立するという説明をそのまま使えない。

根付き集約は、定数個の状態を一辺あたり定数時間で合成できれば、根と処理順を作る前処理も含めて時間 O(N)O(N)、隣接リスト・状態・探索用領域を含めて空間 O(N)O(N)。全方位でも、結合的な合成と空集合の単位元があり、一方向を除く合成を隣接方向数に比例する時間でまとめて作れるなら、同じ時間・空間で求められる。送信先ごとに他の全方向を走査し直すと、星形の木で二乗時間になる。

子の順に依存する演算では順序を保持する。状態が多項式や容量配列ならその長さと合成費用を含め、木だから線形と結論しない。葉では空集合から自身を加え、一頂点だけの木でも距離和は0となる。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。部分木から親へ渡す要約を定め、根の移動やpath上の合成へ進む入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 木構造。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-tree-aggregation

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • heap番号で暗黙に表された完全二分木の区間算術、木上パスの連続区間分解、重心による再帰分解、および更新のためのTop Tree cluster化。

根拠

ABC220 Fの公式問題文・公式解説を2026-10-29に再照合した。公式解説は、全頂点からの距離和を、部分木サイズと根の移動による差分で線形時間に求める方針を示す。上のメッセージ表現と4頂点の小例は、その方針を一般の集約へつなぐための本書独自の説明である。