基準点からの木距離・剰余類・直径・中心

概要

木距離の剰余類による構造分類

木の一つの基準点から各頂点への距離を求め、距離の剰余類と局所構造から頂点の役割や周期的な部品構造を分類する。

木距離・直径・中心・最遠点

木の一意経路距離を少数の基準点から一括計算し、距離label・直径端点・中心・最遠点性質で頂点集合の距離条件を整理する。

考え方

木では二頂点を結ぶ単純な経路が一つしかない。そのため、基準点から一度探索すれば全頂点への距離が分かる。さらに、辺長が非負なら、全頂点それぞれの最遠距離を知りたいときも、始点ごとの探索は不要である。木の直径の両端だけを、全始点に共通する最遠点の候補として残せる。まずこの代表性を示し、その後で直径を求める方法へ進む。

一意経路から距離を求める

頂点数を NN とし、二頂点 u,vu,v を結ぶ経路上の辺長の和を d(u,v)d(u,v) と書く。無重み木では各辺の長さを1とする。根を一つ決め、根の距離を0、親から子への距離を「親までの距離+その辺の長さ」としてDFSで伝えればよい。重み付きでも経路が一意なので、優先度付きキューで距離を確定する必要はない。

任意の二頂点間の距離が必要なら、根からの距離と最小共通祖先(LCA)を使う。w=LCA⁡(u,v)w=\operatorname{LCA}(u,v) とすると、根から ww までを二重に数えた分を引いて

d(u,v)=d(root,u)+d(root,v)−2d(root,w)d(u,v)=d(\mathrm{root},u)+d(\mathrm{root},v) -2d(\mathrm{root},w)

となる。LCA取得の前処理と手順はancestor query・LCAで扱う。

直径から伸びる枝は、両端への長さを超えない

ここからは辺長がすべて非負の木を考える。全頂点対の距離の最大値を直径長 DD とし、それを達成する二頂点を a,ba,b とする。aa から bb への経路を PP と書く。

小例として、次の木を考える。線の横の数は辺長である。

      x     v
      |1    |1
a--2--p--2--q--2--b

aa から bb までの長さは6で、これが直径である。vv から枝先の xx へ行くには、q,pq,p を通って長さ4だけ進む。一方、pp で枝へ入らず aa まで進むと、最後の長さが1から2に増え、d(v,a)=5d(v,a)=5 となる。枝先へ曲がる代わりに、直径上で遠ざかる向きへ進めば損をしない。この比較を任意の枝について示したい。

任意の頂点 xx から PP へ向かう経路が最初に合流する頂点を pp とし、xx の PP 上への射影と呼ぶ。木の経路が一意なので合流点も一意であり、xx が PP 上なら p=xp=x である。枝の長さを h=d(x,p)h=d(x,p) とおく。

a,xa,x 間も b,xb,x 間も直径長以下である。それぞれの経路が pp を通ることから、

d(a,p)+h≤D=d(a,p)+d(p,b),d(b,p)+h≤D=d(b,p)+d(p,a)\begin{aligned} d(a,p)+h&\leq D=d(a,p)+d(p,b),\\ d(b,p)+h&\leq D=d(b,p)+d(p,a) \end{aligned}

となり、

h≤min⁡{d(a,p),d(p,b)}h\leq\min\{d(a,p),d(p,b)\}

を得る。枝がこの上界を超えると、枝先と直径の片端を結ぶ経路が現在の直径より長くなってしまう。

照会点の位置に合わせて、遠ざかる側の端を選ぶ

最遠距離を知りたい頂点を vv とし、その PP 上への射影を qq とする。任意の候補 xx について、射影 pp と qq の並びで比較する端を選ぶ。

qq が aa から pp までの経路上にあるなら、pp から見て反対側の端 bb へ進む。先ほどの h≤d(p,b)h\leq d(p,b) を使うと、

d(v,x)≤d(v,q)+d(q,p)+h≤d(v,q)+d(q,p)+d(p,b)=d(v,b)\begin{aligned} d(v,x)&\leq d(v,q)+d(q,p)+h\\ &\leq d(v,q)+d(q,p)+d(p,b)\\ &=d(v,b) \end{aligned}

となる。最後は vv から bb への一意経路をそのまま足している。qq が pp から bb までの経路上なら、左右を入れ替えて d(v,x)≤d(v,a)d(v,x)\leq d(v,a) を得る。p=qp=q でもこの比較は成り立つ。

最初の不等号を等号にしてはいけない。v,xv,x が直径から伸びる同じ枝の途中にいるときは、両者を結ぶ経路が直径まで戻らない場合がある。射影を経由する歩き方は迂回になり得るが、辺長が非負なので実際の距離の上界にはなる。

従って、どの頂点 xx も二端点より遠くならない。一方、a,ba,b 自身も候補なので、頂点集合を VV と書くと、

E(v):=max⁡x∈Vd(v,x)=max⁡{d(v,a),d(v,b)}E(v):=\max_{x\in V}d(v,x) =\max\{d(v,a),d(v,b)\}

となる。E(v)E(v) を vv の最遠距離、または離心率と呼ぶ。直径端は最遠頂点をすべて列挙するものではなく、各始点の最大距離を達成する候補を少なくとも一つ残すものである。

中心を使うと、二回の最遠点探索も証明できる

直径端が既知なら代表性を使えるが、直径端をどう求めるかはまだ示していない。そのために、直径の中点を基準に同じ式を読み直す。

辺の内部も点として許し、PP の中点を cc、R=D/2R=D/2 とする。vv の射影 qq について t=d(a,q)t=d(a,q)、g=d(v,q)g=d(v,q) とおくと、

E(v)=g+max⁡{t,D−t}=R+g+∣t−R∣=R+d(v,c)\begin{aligned} E(v)&=g+\max\{t,D-t\}\\ &=R+g+|t-R|\\ &=R+d(v,c) \end{aligned}

である。最後は vv から中点 cc へ至る経路の長さである。この式は辺内部の点にも同じ射影の議論で成り立つ。従って、中点から遠ざかった分だけ最遠距離が増える。連続的に点を選べるときの最小値は RR で、中点 cc がそれを達成する。頂点から選ぶ中心は E(v)E(v) を最小にする頂点、すなわち cc への距離が最小の頂点である。零辺があれば、cc から距離0の点も同じ最小値を達成する。

次に、任意の始点 ss から最も遠い頂点 uu を一つ選ぶ。この uu が直径の端になれることを示す。証明のために固定した直径から定めた c,Rc,R はそのまま使う。上の式と三角不等式より、

R+d(s,c)=E(s)=d(s,u)≤d(s,c)+d(c,u)R+d(s,c)=E(s)=d(s,u) \leq d(s,c)+d(c,u)

だから d(c,u)≥Rd(c,u)\geq R である。一方、中点 cc からの最遠距離は RR なので d(c,u)≤Rd(c,u)\leq R。従って d(c,u)=Rd(c,u)=R となり、再び上の式から E(u)=2R=DE(u)=2R=D を得る。そこで uu から最遠の頂点 ww を一つ選べば d(u,w)=Dd(u,w)=D となり、直径の両端が得られる。

この証明は最遠点の一意性を使わない。零辺や同率最遠があっても任意の最大値の頂点を選べる。全辺長が0なら D=0D=0 で、同じ頂点を両端としても距離の式は成り立つ。一頂点の木も a=b=sa=b=s として扱える。

実際の処理は次の三回の探索でよい。

  1. 任意の始点 ss から全頂点への距離を求め、最大の頂点 aa を選ぶ。
  2. aa からの距離配列 dad_a を保存し、最大の頂点 bb を選ぶ。この時点で直径長は da[b]d_a[b] である。中心や経路も必要なら、この探索の親配列で bb から aa への経路を復元する。
  3. bb からの距離配列 dbd_b を保存する。全頂点について E(v)=max⁡{da[v],db[v]}E(v)=\max\{d_a[v],d_b[v]\} とする。

「二回の探索」は直径を得るまでの回数であり、全頂点の最遠距離には最後の一回も使う。重み付きの木でも、各探索は親を避けるDFSで距離を足せばよい。無重みならBFSでもよい。

指定距離・中心・番号条件への使い分け

  • ABC267 F「Exactly K Steps」では、無重みなので、非負整数 KK に対し、vv から距離 KK の頂点が存在する条件は K≤E(v)K\leq E(v) である。十分長い方の直径端への経路には、距離0から E(v)E(v) までの整数距離の頂点が順に並ぶ。その経路の KK 個先を祖先照会で取り出せばよい。質問数を QQ とし、質問を先読みして各端を根とするDFS中の経路配列を使えば、二つの根で合計 O(N+Q)O(N+Q) 時間で答えられる。一般の重み付き木では途中の距離を飛ばすので、K≤E(v)K\leq E(v) だけでは存在を保証しない。
  • ABC221 F「Diameter set」では、直径の中点を共通の基準にできる。ただし、最遠距離の式だけでは、選んだ全頂点対が距離 DD になるとはいえない。無重み木で DD が偶数なら中心頂点の異なる枝から、中心から距離 D/2D/2 の頂点を高々一つずつ選ぶ。同じ枝の二点は経路が中心の手前で合流し、距離が DD 未満になるためである。DD が奇数なら中央辺の両側から、各側の端点を基準に距離 (D−1)/2(D-1)/2 の頂点を一つずつ選ぶ。この追加の条件から、枝ごとの個数を使う数え上げへ進む。
  • ABC428 E「Farthest Vertex」では、最遠距離に加え、同距離で番号最大の頂点が必要になる。任意に選んだ直径端ではこの番号条件まで代表できない。中心1、葉2・3・4の星なら、直径端を2・3にすると中心からの答え4を落とす。公式解説は、各頂点 ii に長さ iεi\varepsilon の補助辺と葉 i′i' を付ける。例えば 0<ε<1/(2N)0<\varepsilon<1/(2N) とすれば、元の頂点 vv から葉への距離 d(v,i)+iεd(v,i)+i\varepsilon は整数距離を優先し、同距離のときだけ番号順になる。この拡張木の直径端には代表性を適用できる。実装で微小な浮動小数を使わず、探索時から距離と番号を比較する方法への接続は問題解説で扱う。

ABC222 F「Expensive Expense」も、行先だけの加点を補助葉へ移してから代表性を使う。ただし自分の補助葉を除外する条件が残るため、除外後も反対端で足りる理由を問題解説で確認する。

距離の偶奇と一般の剰余を区別する

無重み木で根からの距離を depth⁡[v]\operatorname{depth}[v] とすると、隣接頂点では深さの偶奇が反転するので二部彩色になる。LCA距離公式の最後の項は偶数だから、

d(u,v)≡depth⁡[u]+depth⁡[v](mod2)d(u,v)\equiv\operatorname{depth}[u]+ \operatorname{depth}[v]\pmod 2

が成り立つ。一方、一般の法 mm では −2depth⁡[LCA⁡(u,v)]-2\operatorname{depth}[\operatorname{LCA}(u,v)] が消えるとは限らない。距離の剰余で構造を分類するときは、根距離だけで決まると仮定せず、元の構造によって分岐点の深さも制御できるかを調べる。

成立条件と計算量

木の隣接リスト、距離配列と探索スタックはいずれも O(N)O(N) 空間で持てる。一回の探索は全辺を定数回ずつ調べるので O(N)O(N) 時間であり、直径・全最遠距離・頂点の中心まで、上記の定数回の探索と走査を合わせて O(N)O(N) 時間・空間で求められる。LCAを使う場合はその前処理も別に数え、ダブリングなら前処理に O(Nlog⁡N)O(N\log N) 時間・空間、距離照会に O(log⁡N)O(\log N) 時間を使う。

直径端の代表性と二回探索は非負辺長が前提である。例えば一本道の辺長が順に 5,−10,65,-10,6 なら、左端からの最遠点は左から2番目だが、そこからの最遠距離は5で、真の直径長6を得られない。負辺を許す問題へそのまま転用しない。長い一本道では再帰の深さも NN になるので、実装では反復DFSも選べるようにする。距離の剰余を使う分類では、実際の距離と剰余だけの情報も分ける。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。一意経路と直径端点の性質を理解し、少数の距離計算で全頂点を評価する。

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

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

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

習得する技能

  • 木の一つの基準点から全頂点への距離を求め、距離の剰余類と局所構造から各頂点の役割や周期的な部品構造を分類できる。
  • 一回または二回の木探索で少数の基準点からの距離を求め、一意経路・直径端点・中心の性質から頂点分類や最遠距離条件を整理できる。

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: 加法的tree metric復元。

木を探索して基準点から距離labelを作る方法を土台に、距離剰余類による構造分類と、直径端点・中心が距離構造を代表する性質を区別して学ぶ。

このUnitでは扱わないもの

  • 根付き木の子状態を合成する木DP、およびLCA・HLDによるパスの区間分解。

根拠

2026-10-29にABC267 F・ABC221 F・ABC428 Eの公式問題文と個別公式解説を再照合した。射影による枝長の上界からの代表性と、中心からの距離を使う二回探索の証明は、本単元で補った論証である。