virtual tree・auxiliary tree
選択頂点と隣接LCAだけをEuler順にstack接続し、必要な祖先関係を保つ小木を構築する。
この典型を扱う単元: virtual tree・auxiliary tree
検索別名: auxiliary tree、virtual tree、仮想木
未知問からこの典型を見つける手掛かり
- 扱う対象
- Euler順
- LCA
- 選択頂点
- 使う手掛かり
- 少数頂点だけ
- 色ごと
- 重要頂点
- 保つ不変量
- 祖先関係
- 隣接LCA
- 求めるもの
- 小さな誘導木
- 部分集合query
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 木モデルと構造
関連する典型
- ancestor query・LCA: 選択頂点集合を祖先関係を保つ小木へ閉じるため、隣接頂点間のLCAを挿入する。
- Euler順による部分木区間化: 祖先順を保ったstack構築のため、選択頂点をEuler in順に並べる。
学習成果と学習単位
対象頂点と必要なLCAだけをEuler順・stackで結び、元の木上pathを保つvirtual treeを構成できる。
virtual tree・auxiliary treeで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。