ABC 460 F — Farthest Pair Query

考察

黒頂点どうしの最大距離を保つには、頂点集合を二つに分け、それぞれの直径の両端だけを覚えておく。木の距離では、この合計四端点を比べるだけで、二集合を合わせた直径も求められる。この性質を使えば、色が変わった頂点を含む区間だけを更新できる。

各クエリで全黒頂点の対を調べ直すと、最悪で毎回 O(N2)O(N^2) 個の対を比べることになり、N,Q≤105N,Q\leq 10^5 には間に合わない。また、現在の直径の両端だけを全体で一組持つ方法では、その端点が白くなったときに代わりの端点を探し直す必要がある。そこで、小さな集合の直径から大きな集合の直径を作り直せるかを考える。

頂点集合の直径とは、集合内の二頂点間の距離が最大となる経路のことである。距離は元の木上で測り、途中に白頂点があってもよい。以下、二頂点 u,vu,v の距離を d(u,v)d(u,v) と書く。空でない集合 S,TS,T の直径端をそれぞれ a,ba,b と c,dc,d とすると、和集合 S∪TS\cup T の直径端は、この四端点の組合せから選べる。同じ集合内の最大距離は既に分かるため、鍵は「集合をまたぐ最遠の対も端点で代表できる」ことにある。その理由を正当性の節で示す。

この合成をSegment Treeに載せる。葉は頂点番号順に並べ、各節点には、その区間にある黒頂点集合の直径端を保持する。区間は番号で分けるだけでよく、木上で連結である必要はない。

  • 黒頂点 vv の葉は (v,v)(v,v)、白頂点の葉は空集合を表す印とする。一点集合の直径長は0である。
  • 左右とも空でなければ、両方の要約から得る四端点の6対の距離を比べ、最大となる一組を親に保存する。同じ頂点が重複していても、その距離は0なので構わない。
  • 左右どちらかが空なら相手をそのまま返す。両方が空なら空を返す。

初めは全頂点が黒なので、全葉を (v,v)(v,v) として下から構築する。クエリで頂点 xx の色を反転したら、その葉を置き換え、根までの祖先を再計算する。根の要約が全黒頂点集合の直径端なので、その距離を出力すればよい。

距離計算のために、固定した根からの深さ depth⁡(v)\operatorname{depth}(v) と最小共通祖先 LCA⁡(u,v)\operatorname{LCA}(u,v) を求められるよう前処理する。二頂点間の経路は最小共通祖先で折り返すので、

d(u,v)=depth⁡(u)+depth⁡(v)−2depth⁡(LCA⁡(u,v))d(u,v)=\operatorname{depth}(u)+\operatorname{depth}(v) -2\operatorname{depth}\bigl(\operatorname{LCA}(u,v)\bigr)

で距離を計算できる。色だけが変わり木は変わらないため、この前処理は一度でよい。

典型の発動条件

diameter端点のmerge monoid

木上の頂点集合が動的に変わり、最遠距離を保ちたいときは、集合の直径端を要約の候補にする。答えの長さだけでは別集合との距離を比べられないが、端点を残せば和集合の直径を作れる。合成後も次の合成に十分な要約であることと、空集合の扱いまで確かめる。同率の代表がある本問では、端点の組の文字どおりの一致を結合則とみなさず、正しい直径を保持する不変条件で説明する。

LCA距離oracle

固定された木上で多数の二頂点間距離を比較するときは、LCAの前処理を使う。距離を何度でも返すこの仕組みを距離オラクルと呼ぶ。一回の距離取得が定数時間か対数時間かで、Segment Treeの合成費用も変わる。

問題固有の要素

黒頂点集合は木上で連結とは限らない。それでも、元の木上の距離では、集合内のどの頂点からも直径の経路へ一意に合流する。この経路の性質により、集合の直径端が外部点からの最遠候補も代表する。任意の距離空間で二端点だけを残してよいわけではなく、木の一意経路を使う証明が要約の根拠となる。

正当性

空でない頂点集合 UU の直径の端点を a,ba,b とする。まず、任意の w∈Uw\in U と、集合の外も含めた任意の頂点 xx について、

d(x,w)≤max⁡(d(x,a),d(x,b))d(x,w) \leq \max\bigl(d(x,a),d(x,b)\bigr)

を示す。集合が一点なら w=a=bw=a=b なので成り立つ。以下では二点以上とする。

aa から bb への経路を PP とする。ww から PP へ向かう経路が最初に出会う頂点を pp と呼び、ww の PP 上への射影とする。木の経路は一意なので、この合流点も一意である。ww が PP 上なら p=wp=w。経路から伸びる枝の長さを h=d(p,w)h=d(p,w) とおく。

a,ba,b は集合 UU の直径端なので、a,wa,w の距離も b,wb,w の距離も d(a,b)d(a,b) 以下である。これらの経路は pp を通るから、例えば

d(a,p)+h≤d(a,p)+d(p,b)d(a,p)+h \leq d(a,p)+d(p,b)

となる。同様に b,wb,w の距離も比べると、

h≤d(p,b),h≤d(p,a)h\leq d(p,b),\qquad h\leq d(p,a)

を得る。つまり、枝を先端の ww まで進むより、経路 PP をどちらかの端まで進むほうが短くならない。

次に、xx の PP 上への射影を qq とする。qq が aa から pp までの経路上にあるときは、反対側の端 bb と比べる。三角不等式と上の枝の長さの制限から、

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

最後の等号は、xx から bb への経路が q,pq,p をこの順に通るためである。qq が pp から bb までの経路上なら、左右を入れ替えて d(x,w)≤d(x,a)d(x,w)\leq d(x,a) を得る。q=pq=p も含め、これで補題が示された。最初の不等式を等号にしないのは、x,wx,w が同じ枝にいる場合、その最短経路が qq を通るとは限らないためである。

ここで左右の空でない集合を S,TS,T、それぞれの直径端を a,ba,b と c,dc,d とする。集合をまたぐ任意の対 s∈S,t∈Ts\in S,t\in T に対して、まず集合 SS と外部点 tt に補題を使い、次に集合 TT と外部点 a,ba,b に使うと、

d(s,t)≤max⁡(d(a,t),d(b,t))≤max⁡{d(a,c),d(a,d),d(b,c),d(b,d)}.\begin{aligned} d(s,t) &\leq\max\bigl(d(a,t),d(b,t)\bigr)\\ &\leq\max\left\{\begin{aligned} &d(a,c),d(a,d),\\ &d(b,c),d(b,d) \end{aligned}\right\}. \end{aligned}

同じ集合内の対は、その集合の直径長以下である。従って、和集合のどの対も四端点の6対の最大距離以下となる。逆に、その6対はすべて和集合内の対なので、最大距離は和集合の直径長に一致する。

同率の直径端が複数あっても、補題はどの直径端を選んでも成り立つ。例えば中心から三つの葉へ辺が伸びる星型の木では、どの葉二つも直径端となるが、残した二端点で外部点からの最遠距離を表せる。したがって、合成で最大距離を達成する端点を一組選べば、次の合成でも十分である。括り方を変えた結果、端点の組そのものが一致するとは限らないが、直径長と以後の合成に必要な性質は保たれる。

空集合との合成は相手をそのまま返し、一点集合は同じ頂点を両端とする。葉が表す集合について要約は正しく、内部節点でも上の合成によってその区間の正しい直径端を保持する。更新した葉から根まで再計算すれば、この不変条件が復元される。根は全黒頂点集合を表すので、その端点間距離が求める答えである。

実装上の注意

  • 公式入力では、全体の黒頂点は常に2個以上ある。根が空・一点になる場合の出力規約を追加する必要はない。一方、内部節点や葉は空・一点になり得るので、空との合成と (v,v)(v,v) は必ず実装する。葉数を2の冪にそろえる際の余った葉も空とする。
  • 空を表す印を距離計算へ渡さない。同率では最大距離を達成する端点を任意に一組残せばよく、以後の合成も正しい。
  • 合成一回の距離取得は定数回だが、一回のLCA取得の費用も数える。現在の直径長を要約に添えれば、左右それぞれの直径長を再計算せずに使える。

復習の核

  • 動的集合の答えを保つときは、削除に直接対応する代わりに、小集合の要約から全体を作り直せないか考える。
  • 木の直径端を代表として使う理由は、直径経路から伸びる枝が、合流点から両端までの距離を超えないことにある。この補題を二回使って四端点の十分性を示す。
  • 要約の代表が同率で変わっても、次の合成に必要な性質が保たれるかを確認する。問題全体の非空保証とは別に、内部の空集合を扱う。

計算量と制約

時間

ダブリングでLCAを求める方式では、前処理が O(Nlog⁡N)O(N\log N)、距離取得が一回 O(log⁡N)O(\log N)。Segment Treeの構築には O(N)O(N) 回、各更新には O(log⁡N)O(\log N) 回の合成を行い、合成ごとに定数回の距離を取得する。従って構築は O(Nlog⁡N)O(N\log N)、各更新と出力は O(log⁡2N)O(\log^2 N) で、全体は O(Nlog⁡N+Qlog⁡2N)O(N\log N+Q\log^2 N) となる。

オイラーツアーの深さ列に対する区間最小値取得(RMQ)をSparse Tableで行えば、O(Nlog⁡N)O(N\log N) 時間の前処理後にLCAと距離を O(1)O(1) で取得できる。この方式では構築が O(N)O(N)、各更新と出力が O(log⁡N)O(\log N) で、前処理を含む全体は O((N+Q)log⁡N)O((N+Q)\log N) となる。

空間

どちらの方式もLCAの前処理に O(Nlog⁡N)O(N\log N)、木・深さ・色・Segment Treeに O(N)O(N) を使う。全体で O(Nlog⁡N)O(N\log N)。

制約との対応

3≤N≤1053\leq N\leq 10^5、1≤Q≤1051\leq Q\leq 10^5。時間制限は4秒、メモリ制限は1024 MiBである。ダブリング方式は更新ごとに対数因子が二つ掛かるため、距離取得の定数倍にも注意する。定数時間で距離を取得する方式なら、全体を O((N+Q)log⁡N)O((N+Q)\log N) に抑えられる。いずれの方式でも、どの時点でも全体の黒頂点が2個以上あるという保証により、根の端点間距離をそのまま答えにできる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Farthest Pair Query の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間monoid要約

主題
  • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 区間monoid要約

    補助タグ: ancestor query・LCA 木距離・直径・中心・最遠点

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 区間monoid要約

    • 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。

    先に読む単元:

    • ancestor query・LCA — doubling・binary liftingで得た考え方と実装を再利用し、ancestor query・LCAの発動条件・正当化・境界を重複なく学ぶ。
    • 基準点からの木距離・剰余類・直径・中心 — 木を探索して基準点から距離labelを作る方法を土台に、距離剰余類による構造分類と、直径端点・中心が距離構造を代表する性質を区別して学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題