maehara https://blog.hatena.ne.jp/maehara/ TM's memo https://tmaehara-algorithm.hatenablog.com/ 木の頂点 $u$, $v$ について最小共通先祖 (LCA) を計算するシンプルなアルゴリズムを紹介します．複数の頂点の組に対して LCA を求めるのであれば，木を前処理をしてクエリあたり $O(\log n)$ なり $O(1)$ で求めるのが定石ですが，ここではそうでなく，線形時間かけて求めることを考えます．木は親ポインタ parent: &[Option<usize>] によって与えられるとします． O(n) 時間 O(n) 空間アルゴリズム すぐに思いつくアルゴリズムは頂点に訪問済みかどうかをあらわすフラグをもたせて各頂点から親方向に走査するものでしょう．このアルゴリズムは領域の確保に… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftmaehara-algorithm.hatenablog.com%2Fentry%2F2021%2F11%2F17%2F040124" title="Least Common Ancestor O(d) time and O(1) space - TM&#39;s memo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-11-17 04:01:24 rich https://tmaehara-algorithm.hatenablog.com/entry/2021/11/17/040124 1.0 100%