LCA 最近公共祖先

oiwiki参考文章
最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。

以LCA(u,v)表示u和v的最近公共祖先

朴素算法

先将深度大的点向上调整至和小的点相同，然后两个点同时向上移动，直到两个点移动到同一个点
如果这棵树建的比较平衡，用这种方法的时间复杂度为O(logn)，但是遇到一条链特别长的情况时，复杂度可能会退化到O(n)

倍增算法

用F[i][j]来表示i的第2^j个父节点。
先将深度大的点向上调整至与小的点相同，然后从最大的 j 开始不断尝试，直到第一次出现 F[u][j] != F[v][j]，令u = F[u][j]，v = F[v][j]，因为LCA(F[u][j],F[v][j]) = LCA(u,v)。然后继续循环直到u == v
即使在极端条件下时间复杂度也为O(logn)

题目链接

#include 
#include 
#include 
#include 
#define MXN 50007
using namespace std;
std::vector v[MXN];
std::vector w[MXN];

int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;

// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int root, int fno)
{
    // 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
    fa[root][0] = fno;
    dep[root] = dep[fa[root][0]] + 1;
    // 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
    // 2^(i-1) 的祖先节点。
    for (int i = 1; i < 31; ++i)
    {
        fa[root][i] = fa[fa[root][i - 1]][i - 1];
        cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
    }
    // 遍历子节点来进行 dfs。
    int sz = v[root].size();
    for (int i = 0; i < sz; ++i)
    {
        if (v[root][i] == fno) continue;
        cost[v[root][i]][0] = w[root][i];
        dfs(v[root][i], root);
    }
}

// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y)
{
    // 令 y 比 x 深。
    if (dep[x] > dep[y]) swap(x, y);
    // 令 y 和 x 在一个深度。
    int tmp = dep[y] - dep[x], ans = 0;
    for (int j = 0; tmp; ++j, tmp >>= 1)
        if (tmp & 1) ans += cost[y][j], y = fa[y][j];
    // 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
    if (y == x) return ans;
    // 不然的话，找到第一个不是它们祖先的两个点。
    for (int j = 30; j >= 0 && y != x; --j)
    {
        if (fa[x][j] != fa[y][j])
        {
            ans += cost[x][j] + cost[y][j];
            x = fa[x][j];
            y = fa[y][j];
        }
    }
    // 返回结果。
    ans += cost[x][0] + cost[y][0];
    return ans;
}

int main()
{
    // 初始化表示祖先的数组 fa，代价 cost 和深度 dep。
    memset(fa, 0, sizeof(fa));
    memset(cost, 0, sizeof(cost));
    memset(dep, 0, sizeof(dep));
    // 读入树：节点数一共有 n 个。
    scanf("%d", &n);
    for (int i = 1; i < n; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        ++a, ++b;
        v[a].push_back(b);
        v[b].push_back(a);
        w[a].push_back(c);
        w[b].push_back(c);
    }
    // 为了计算 lca 而使用 dfs。
    dfs(1, 0);
    // 查询 m 次，每一次查找两个节点的 lca 点。
    scanf("%d", &m);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d %d", &a, &b);
        ++a, ++b;
        printf("%dn", lca(a, b));
    }
    return 0;
}