2017 February 22

最近公共祖先

对于有根树T的两个结点u和v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u和v的祖先且x的深度尽可能得大。

最近公共祖先有多种求法，下面介绍常见的几种。

朴素解法

这种解法相当于找相交链表的第一个交点：可以先将深度大的节点往上调使两节点深度相同，然后两个节点一起往上调，直到两个节点相同为止；也可以任选一个节点记录它到根节点的路径经过的所有节点，然后从另一个节点往上走，经过的第一次出现在记录中的节点即为所求。

转化为RMQ求解

转化时又有两种做法：

一种是先根遍历求出一个长度为2n-1的序列seq[]以及对应的深度h[][0]，并维护各点第一次出现在序列中的位置first[]，预处理出区间深度最小值h[][]，那么求u和v的LCA转化为求区间first[u]和first[v]内深度取最小值对应的点。

另一种采用树上倍增思想，记f[i][j]表示节点i的2^j的祖先，那么显然f[i][0]为父节点，f[i][j] = f[f[i][j-1]][j-1]，求u和v的LCA时，先将深度大的节点往上调到与另一节点同一高度，然后一起往上调。

int n, m, u, v, f[100005][20], h[100005];
vector<int> g[100005];
void dfs(int c, int d, int p) {
    h[c] = d; f[c][0] = p;
    for (size_t i = 0; i < g[c].size(); i++)
        if (g[c][i] != p)
            dfs(g[c][i], d + 1, c);
}
int lca(int x, int y) {
    if (h[x] < h[y]) swap(x, y);
    int d = h[x] - h[y];
    for (int i = 19; i >= 0; i--) {
        if ((1 << i) & d)
            x = f[x][i];
    }
    if (x == y) return x;
    for (int i = 19; i >= 0; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1, 1);
    for (int j = 1; j <= 19; j++)
        for (int i = 1; i <= n; i++)
            f[i][j] = f[f[i][j-1]][j-1];
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

两种做法都是在线的，第2种做法的时空间复杂度稍更优一些。

Tarjan算法

树链剖分做法

这是另外一种在线做法，思路是先做树链剖分，然后分别处理各种询问。

例如，询问LCA(a, b)：

const int N = 500005;
int n, m, s, a, b;
int fa[N], dep[N], siz[N], son[N], top[N];
vector<int> g[N];
void dfs1(int x, int u, int h) {
    fa[x] = u; dep[x] = h; siz[x] = 1;
    for (auto v : g[x]) {
        if (v != u) {
            dfs1(v, x, h + 1);
            siz[x] += siz[v];
            if (siz[v] > siz[son[x]])
                son[x] = v;
        }
    }
}
void dfs2(int x, int u, int t) {
    top[x] = t;
    if (son[x] == 0) return;
    dfs2(son[x], x, t);
    for (auto v : g[x]) {
        if (v != u && v != son[x])
            dfs2(v, x, v);
    }
}
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]])
            u = fa[top[u]];
        else
            v = fa[top[v]];
    }
    return dep[u] < dep[v] ? u : v;
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs1(s, 0, 1);
    dfs2(s, 0, s);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

应用

Table of Contents