ancestor query・LCA
根付き木の祖先関係を時刻またはbinary liftingで索引化し、LCAと木上距離を答える。
この典型を扱う単元: ancestor query・LCA
検索別名: LCA、ancestor query、最小共通祖先
未知問からこの典型を見つける手掛かり
- 扱う対象
- 二頂点
- 根付き木
- 祖先
- 使う手掛かり
- 共通祖先
- 木上距離
- 保つ不変量
- 深さ
- 祖先表
- 求めるもの
- LCA
- ancestor判定
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 木モデルと構造
関連する典型
学習成果と学習単位
binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。
ancestor query・LCAで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC267 F「Exactly K Steps」 公式問題主題: 基準点からの木距離・剰余類・直径・中心 / 補助タグ
- ABC294 G「Distance Queries on a Tree」 公式問題主題: Euler順による部分木区間化 / 主タグ
- ABC298 Ex「Sum of Min of Length」 公式問題主題: ancestor query・LCA / 主タグ
- ABC329 G「Delivery on Tree」 公式問題主題: 根付き木DP・部分木集約 / 補助タグ
- ABC405 F「Chord Crossing」 公式問題主題: laminar区間族の包含木構築 / 補助タグ
- ABC438 F「Sum of Mex」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC460 F「Farthest Pair Query」 公式問題主題: 区間monoid要約 / 補助タグ