LCA(最近公共祖先)

今天学习了LCA算法的两种做法，tarjan和树上倍增(本质上是暴力求解的优化)。

tarjan求解LCA

该算法利用并查集缩点，离线求每个询问的两点LCA。
首先将所有点对相互储存在树上(如果要求点 $x$ 和点 $y$ 的LCA，那么将 $y$ 存在 $x$ 中作为一次询问，将 $x$ 也存在 $y$ 中)，然后对树进行一次后序遍历。 在后序遍历过程中，每访问一个点，需要遍历该点的所有询问点对，如果询问点已经被访问过了，那么这两点的最近公共祖先为询问点所在的父亲节点(每次访问完一个点后，需要将它和它的所有儿子合并在 它的父亲节点中，这个操作可以用树上并查集来实现)。
P3379 【模板】最近公共祖先（LCA）

在完成该题的过程中，遇到一个问题：用for循环遍历vector时计算了.size()-1，.size()的返回值是unsigned的，如果vector为空，返回0再减1，会导致RE。因此需要强转一下int类型，或者先把.size()赋值给int变量来用。

int n, m, s, vis[500010], ans[500010], fi[500010];
struct Node {
    int father;
    vector<int> nex, sol, id;
} t[500010];
int find(int x) { return fi[x] == x ? x : fi[x] = find(fi[x]); }
void q(int u, int v, int i) {
    t[u].sol.pb(v);
    t[u].id.pb(i);
}
void dfs(int x) {
    vis[x] = 1;
    for (auto it : t[x].nex) {
        if (!vis[it]) {
            dfs(it);
            fi[it] = x;
        }
    }
    rep(i, 0, (int)t[x].sol.size() - 1) {
        int y = t[x].sol[i];
        if (vis[y]) {
            ans[t[x].id[i]] = find(y);
        }
    }
    return;
}
int main() {
    ios;
    cin >> n >> m >> s;
    rep(i, 0, n) fi[i] = i;
    rep(i, 0, n - 2) {
        int u, v;
        cin >> u >> v;
        t[u].nex.pb(v);
        t[v].nex.pb(u);
    }
    rep(i, 0, m - 1) {
        int u, v;
        cin >> u >> v;
        q(u, v, i);
        q(v, u, i);
    }
    dfs(s);
    rep(i, 0, m - 1) { cout << ans[i] << endl; }
    return 0;
}

倍增求解LCA

考虑一种暴力的解法，每次将两点中较深的一点上移至它的父亲节点，直到两点相遇。单次查询时间复杂度为 $O(n)$ ，效率较低。
暴力解法因为每次单点上移一位而效率较低，可以使用树上倍增的思想对其进行优化，每次向上移动至它的 $2^i$ 级祖先，从而使 $O(n)$ 的线性复杂度优化为对数复杂度 $O(nlogn)$ 。
具体操作上，我们先预处理出每个节点的 $2^i$ 级祖先(节点的 $2^i$ 级祖先是它的 $2^{i-1}$ 级祖先的 $2^{i-1}$ 级祖先)和节点深度，然后先将两点中较深的一点用倍增的方式升高直至两点深度相同，然后再一起进行倍增向上，终止条件是两点的父节点相同。这一查找过程可以类比二进制数来理解。
可以用dp预处理出对数表，方式在以下代码中。

struct Node {
    int depth;
    vector<int> nex;
    vector<int> fa = vector<int>(32, 0);
} t[500010];
int n, m, s, vis[500010], lg[500010];
void dfs(int x, int father) {
    vis[x] = 1;
    t[x].depth = t[father].depth + 1;
    t[x].fa[0] = father;
    rep(i, 1, lg[t[x].depth - 1]) { t[x].fa[i] = t[t[x].fa[i - 1]].fa[i - 1]; }
    for (auto it : t[x].nex) {
        if (!vis[it])
            dfs(it, x);
    }
}
int LCA(int x, int y) {
    if (t[x].depth < t[y].depth) {
        swap(x, y);
    }
    while (t[x].depth > t[y].depth) {
        x = t[x].fa[lg[t[x].depth - t[y].depth]];
    }
    if (x == y)
        return x;
    per(i, lg[t[x].depth - 1], 0) {
        if (t[x].fa[i] != t[y].fa[i]) {
            x = t[x].fa[i];
            y = t[y].fa[i];
        }
    }
    return t[x].fa[0];
}
int main() {
    ios;
    cin >> n >> m >> s;
    rep(i, 1, n) { lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); }
    rep(i, 1, n) lg[i]--;
    rep(i, 0, n - 2) {
        int u, v;
        cin >> u >> v;
        t[u].nex.pb(v);
        t[v].nex.pb(u);
    }
    dfs(s, 0);
    rep(i, 0, m - 1) {
        int x, y;
        cin >> x >> y;
        cout << LCA(x, y) << endl;
    }
    return 0;
}