ABC 267 F — Exactly K Steps

考察

木の直径端点をL,Rとすると、任意の頂点uから最遠の頂点の一つはLまたはRである。uから距離Kの頂点がどこかに存在すれば、uからLまたはRへのpathのうち長さK以上の方に、距離ちょうどKの頂点が必ずある。root Xでuの深さがK以上なら、path stackの深さ depth(u)−K の頂点がuからX方向へK進んだ答えになる。

棄却する候補: 各queryでuからBFSし、距離Kの頂点を探す。

木全体の探索をQ回繰り返すことになる。

採用する候補: 直径端点L,Rをそれぞれ根にDFSし、root-to-current path stackからuのK個上の祖先をquery回答候補として二回調べる。

uから各端点へのpathは根付き木の祖先列であり、直径性により二本のどちらかを試せば存在する全queryを覆う。

arbitrary-distance witness queryをdiameter endpoint coverで二つのlevel-ancestor queryへ帰着し、offline DFS stackで解く。

典型の発動条件

木の直径端点による最遠点cover

発動条件: 任意頂点から指定距離のwitnessを一つ求め、方向を全分岐へ探したくないとき。

直径両端への二本のpathだけを候補にし、いずれか十分長い方から頂点を取る。

offline level ancestor

発動条件: 固定rootの木で、各頂点に付いた祖先深さqueryをまとめて答えるとき。

DFS中のroot-to-current pathをstackに保ち、対象深さを配列indexで参照する。

問題固有の要素

必要なのは任意の一頂点なので、uを中心とする距離K球全体を表現せず、直径方向の一つのwitnessへ限定できる。

別の問題へ持ち帰る視点: witness queryは全候補を列挙するより、必ず候補を含む少数のcanonical pathを探す。

正当性

任意uの最大距離は直径端a,bのいずれかで達成される。距離K点があれば少なくとも一端へのpath長≥KなのでそのpathのK歩点を返せる。a,b根DFSのancestor stackがpath上の所要点を正確に取得する。

実装上の注意

  • 任意頂点から最遠点Lを求め、Lから最遠点Rを求める二回のDFS/BFSで直径端点を得る。
  • 各queryを頂点uへ付け、L根の走査で未回答ならR根の走査を試し、両方でdepth<Kなら−1にする。

復習の核

  • 木で指定距離の任意点を求める問題は、直径端点へのpathが全距離を代表できないか確認する。
  • queryを先読みできるlevel ancestorはbinary liftingを作る前にDFS path stackで線形処理できるか検討する。

計算量と制約

時間

N頂点Q質問。直径探索O(N)、二root DFS stack回答O(N+Q)。

空間

木、質問list、depth stack O(N+Q)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1); The given graph is a tree.; 1 \leq Q \leq 2 \times 10^5; 1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q); All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Exactly K Steps の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 基準点からの木距離・剰余類・直径・中心

主題
追加で学ぶ技能
    なし
    既習技能
    • ancestor query・LCA: binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。

    主タグ: 木距離・直径・中心・最遠点

    補助タグ: ancestor query・LCA

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

    学習の位置

    体系上の位置: 基準点からの木距離・剰余類・直径・中心

    • 一回または二回の木探索で少数の基準点からの距離を求め、一意経路・直径端点・中心の性質から頂点分類や最遠距離条件を整理できる。

    先に読む単元:

    • ancestor query・LCA — doubling・binary liftingで得た考え方と実装を再利用し、ancestor query・LCAの発動条件・正当化・境界を重複なく学ぶ。

    この解説で扱わないこと:

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題