差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:graph_theory:lowest_common_ancestor [2019/12/26] – ikatakos | programming_algorithm:graph_theory:lowest_common_ancestor [2019/12/26] – [ダブリング] ikatakos | ||
|---|---|---|---|
| 行 101: | 行 101: | ||
| $k$ が小さい方から順に全頂点を埋めていくと、$k$ を求める際には $k-1$ の結果を利用できる。 | $k$ が小さい方から順に全頂点を埋めていくと、$k$ を求める際には $k-1$ の結果を利用できる。 | ||
| - | 最も深い頂点が1発で根にたどり着けるような $k$ で止める。 | + | 最も深い頂点が1発で根を通り越すような $k$ の直前で止める。 |
| == $a,b$ の深さを合わせる == | == $a,b$ の深さを合わせる == | ||
