はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるLCA問題まとめ

LCA

  • Lowest Common Ancestor
  • 根付き木のある2頂点u,vの共通祖先で最も根から遠い頂点を高速に見つけること
  • yukicoder上でのantaさんの解説
  • アルゴリズムはいくつかある「ダブリング」「HL分解」「RMQ使用」RMQが最速っぽいけど、体感HL分解の方が早いような…
  • LCA+根からある頂点への情報(深さとかコスト和とか)を使う解法が多い

例) 頂点aから頂点bへの距離はdist(根,a) + dist(根,b) - 2*dist(根,lca(a,b))となる

  • LCAは単体では余り使われないので、これだけ知っててもしょうがなかったりするが、無いと解けない問題はある

【発展的話題】木のある頂点集合から、その集合とそのLCAからなる頂点集合を得るには

この問題で出てきた

1. dfsで木の頂点をpost-orderで番号付けする

int tout[301010], dep[301010], k;
void dfs(int cu, int pa = -1) {
    for (int to : E[cu]) if (to != pa) {
        dep[to] = dep[cu] + 1;
        dfs(to, cu);
    }
    tout[cu] = k; // ← ここ!
    k++;
}

2. 木のある頂点集合をpost-order昇順でソートするが、頂点集合に番兵として根も追加しておく

v.push_back(0);
sort(v.begin(), v.end(), [&](int a, int b) { return tout[a] < tout[b]; });

こうすることで深い所から順に処理できる。

3. 隣り合う二頂点についてLCAをとって、それを頂点集合にまとめると完成

int n = v.size();
rep(i, 0, n - 1) {
    int l = lca(v[i], v[i + 1]);
    v.push_back(l);
}
sort(v.begin(), v.end(), [&](int a, int b) { return tout[a] < tout[b]; });
v.resize(unique(v.begin(), v.end()) - v.begin());

ちなみに、この頂点集合間である頂点とその親について下から処理をしていきたい時は、以下のようにやる
(この問題ではimos方法的な手法で個数を上に伝搬させる必要があってやった)
v[i]の親はlca(v[i], v[i + 1])になるのを利用。
あと、番兵のお陰で一番最後は0となるので、これだけ別途で上手くやる。

rep(i, 0, v.size() - 1) {
    int l = lca(v[i], v[i + 1]);
    imos[l] += imos[v[i]];
    ans[imos[v[i]]] += dep[v[i]] - dep[l];
}
ans[imos[0]]++;

作った解法はこれです