木の均衡分離点から重心分解へ進む

概要

木の均衡分離点と重心分解

非負重みの各成分を半分以下にする一点を選ぶ。頂点数を重みとし各成分で繰り返すと、対数深さの重心分解を得る。

一点の均衡分離点

木の各頂点に非負重みを置き、総和をWとする。ある頂点を除いて重みW/2を超える成分があれば、その方向へ進む。戻る側の重みはW/2未満なので後戻りせず停止し、各成分が半分以下の一点を得る。部分木重みと親側の重みをDFSで求めてもO(N)。ABC453 Fの重みは元の葉の個数であり、通常の頂点数ではない。

再帰利用による重心分解

頂点数を重みにして重心を除き、各残存成分で再び重心を選ぶ。成分サイズが半減するため深さO(log N)、各段を線形走査して全体O(N log N)。ABC291 Exで分解木そのものを構成し、ABC359 Gで重心を通るpairだけを集計する。葉数による一点選択だけから頂点数の対数深さを主張してはいけない。

考え方

非負重みの木で、頂点を除いた各成分の重みが総重みの半分以下となる点を選ぶ。頂点数を重みにして再帰的に分ける重心分解は、各段でサイズが半減する。

部分木重みから一点を選び、分解木を作る

処理対象の成分で根を仮に一つ決め、sub[v]=w_v+Σ_child sub[child]をpostorderで求める。総重みWに対し、vを消した後の最大成分重みはmax(W−sub[v],各childのsub[child])。全vを走査してこの値がW/2以下の頂点を選ぶ。W=0ならどの頂点でもよい。存在性は半分を超える側へ進む議論から従う。

頂点数重心の再帰ではw_v=1とする。重心cを分解木の頂点にし、removed[c]=trueとして、未削除の各隣接成分を別々に再帰する。その成分の重心をcの子にする。subは今回の未削除成分だけで計算し、元の木で一度作った部分木サイズを使い回さない。各成分の頂点数は半減し、同じ再帰深さでは成分が互いに素なので、一段O(N)、全体O(N log N)である。

重心を通るpairを一度だけ集計する

cを消した各隣接成分から、頂点vの色と距離d(c,v)を列挙する。色ごとに、既に処理した成分の個数cntと距離和sumを持ち、最初はc自身だけを距離0で登録する。新しい成分内のvについて、同色頂点との距離和へcnt·d(c,v)+sumを加える。その成分の全queryを終えてから、全vの個数と距離を登録する。同じ成分の頂点同士をこの段では数えず、再帰へ渡すためである。

異なる成分の二点間の一意pathはcを通るので距離は二距離の和となる。各頂点対は初めて別成分へ分かれる重心で一回だけ集計され、c自身とのpairも同じ式に入る。色索引の操作がO(1)なら分解全体O(N log N)、平衡木ならその索引費用を掛ける。毎成分で全色域を初期化せず、今回使う色だけを片付ける。

成立条件と計算量

一点の選択はO(N)、頂点数重心による全分解はO(N log N)。葉数など別の重みを使う一点選択から、頂点数の対数深さを主張しない。pathの集約では重心を通るpairだけを重複なく数える。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。重み付きの一点分離と、頂点数を半減させる再帰分解を区別し、分離点を通る寄与を集計する。

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

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

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

習得する技能

  • 各連結成分の重心を選び、除去後の成分サイズが半分以下になる再帰分解木を構成できる。
  • 非負頂点重みの総和に対し、除去後の各成分を半分以下にする一点を線形時間で選び、通常の頂点数重心と葉数重心を区別できる。

前提と範囲

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

直接の前提単元: なし。

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

部分木重みから一点の均衡分離点を選ぶ基本を学び、頂点数重みで再帰利用すると各成分が半減して深さを抑えられることを示す。

このUnitでは扱わないもの

  • LCA・HLDによる固定木上パスの区間分解。

根拠