考察
木の直径端点を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.
出典