LCA

keyword:lca

カートに追加

overview

根付き木が与えられたとき,準備O(NlogN),次のクエリにO(1)で答えるアルゴリズム・データ構造. - 頂点u,vに共通する最も若い祖先 LCA問題は,構築処理さえ済めば各質問をRMQの時間で解くことが出来る. ループを含むグラフを与えた場合,再帰処理が終わらない可能性がある.

usage

LCATable(const Graph& graph, int root = 0)
; rootを根としたgraphに対してLCAを構築する
int LCATable::operator()(int u, int v)
; 頂点u,vに共通する最も若い祖先の頂点番号を取得する

verified

problem.

references

thanks.

require

code