LCA倍增 模板

LCA倍增 最近公共祖先

构造 NlogN 查询 ogN

先调用pre()构造对数数组 再调用dfs(root, 0, 0)查询深度 再调用work()构造跳表

最后调用lca(u, v)查询在有根树中节点u和v的最近公共祖先

const int N = 10005;
struct edge  { int to, next; } e[N << 1];
int n, head[N];
namespace LCA
{
    int log[N], depth[N], deg[N], par[N][30];
    inline void pre()
    {
        log[1] = 0;
        for (int i = 2; i < N; ++i)
        {
            log[i] = log[i - 1];
            if ((1 << (log[i] + 1)) == i)   log[i]++;
        }
    }
    void dfs(int u, int fa, int dep)
    {
        depth[u] = dep;
        par[u][0] = fa;
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].to;
            if (v == fa)    continue;
            dfs(v, u, dep + 1);
        }
    }
    inline void work()
    {
        for (int j = 1; j <= log[n]; ++j)
            for (int i = 1; i <= n; ++i)
                par[i][j] = par[par[i][j - 1]][j - 1];
    }
    inline int lca(int u, int v)
    {
        if (depth[u] < depth[v])    std::swap(u, v);

        int t = depth[u] - depth[v];
        for (int j = 0; j <= log[n]; ++j)
            if (t >> j & 1) u = par[u][j];

        if (u == v) return u;

        for (int i = log[n]; ~i; --i)
            if (par[u][i] != par[v][i])
            {
                u = par[u][i];
                v = par[v][i];
            }

        return par[u][0];
    }
}