根が頻繁に変わる木でLCAを求める

根が $r$ のときの頂点 u,vLCA \mathrm{lca}_r (u,v) とする。\mathrm{lca}_0(u,v), \mathrm{lca}_0(u,r), \mathrm{lca}_0(v,r) のうち最も頂点 0 から遠い頂点が \mathrm{lca}_r(u,v) である。

この機能を持ったHL分解のライブラリを書いておく。きちんとした証明はしてないけど多分問題ない。

// Verified at http://codeforces.com/problemset/problem/916/E
struct HLD {
  using Tree = std::vector<std::vector<int>>;
  std::vector<int> parent, head, vid;

  HLD(const Tree &g) : parent(g.size()), head(g.size()), vid(g.size()) {
    int k = 0;
    std::vector<int> size(g.size(), 1);
    std::function<void(int, int)> dfs = [&](int u, int p) {
      for (int v : g[u]) if (v != p) dfs(v, u), size[u] += size[v];
    };
    std::function<void(int, int, int)> dfs2 = [&](int u, int p, int h) {
      parent[u] = p; head[u] = h; vid[u] = k++;
      for (int v : g[u]) if (v != p && size[u] < size[v] * 2) dfs2(v, u, h);
      for (int v : g[u]) if (v != p && size[u] >= size[v] * 2) dfs2(v, u, v);
    };
    dfs(0, -1);
    dfs2(0, -1, 0);
  }

  int lca(int a, int b, int c) {
    while (true) {
      if (vid[a] < vid[b]) swap(a, b);
      if (vid[a] < vid[c]) swap(a, c);
      if (vid[b] < vid[c]) swap(b, c);
      if (head[a] == head[b]) return b;
      a = parent[head[a]];
    }
  }
};