プログラミングコンテストチャレンジブック 4-3 その2

4-3 「グラフマスターへの道」の続きです。

• LCA (Lowest Common Ancestor) - 根つき木の2つのノードの共通の祖先で最も近いもの
  • 二分探索を用いて探索
    • 木の深さに注目して、注目点の深さの均等にしつつ親を探索していくと O(n)
    • いったん LCA に到達すれば後の祖先は全て共通なので、まず同じ深さになるまで深いほうを辿って、2^k 親を辿ったノードを計算して深さについて二分探索する
  • RMQ を用いて探索
    • 木を DFS(深さ優先探索)で訪問順にインデックスを振る(重複あり)。各頂点の最初の訪問時のインデックスを計算する
    • LCA(u, v) = vs[k] ただし k は id[u] <= i <= id[v] で depth が最小になる i
  • Housewife Wind - 木状に繋がった小屋の移動にかかる時間(コスト)を、辺のコストが変化する条件下で繰り返し計算する
    • RMQ を用いる時のように木を DFS 訪問順の1列の並びに展開して LCA からのコストの和で計算できる