线性（？） LCA 的第不知道多少种求法

· · 休闲·娱乐

下文提到的算法看似理论复杂度很优，实则跑不过 dfn 序求 lca，一点用没有，故投稿至休闲娱乐专区。

我们知道树剖的链顶构成的虚树中，最大深度不超过 O(\log n) 级别，这也是树剖暴力跳重链的复杂度保证。但是我们可以优化暴力跳父亲的过程。具体的，我们先进行树剖，之后把这棵虚树拿出来做倍增，倍增跳重链即可。

实际实现的时候可以不建出虚树，而是直接在处理链顶的 dfs 中处理倍增数组。细节不是很多，码量也不是很大，可以做到 O(n\log\log n) 预处理，单次查询 O(\log\log n)，空间复杂度 O(n\log\log n)，而在实际场景中 O(\log\log n) 基本上近似于 O(1)，所以我们可以认为这是一个 O(n)-O(1) 且空间常数较小的 LCA。

以模板题为例，比正常树剖快许多，但是比 dfn 序慢一点，似乎唯一的优势在于空间比 dfn 序小，没什么用，下文是 P3379 代码。

#include <bits/stdc++.h>
#define il inline

using namespace std;

const int N = 5e5 + 5;
const int Inf = 2e9;
template <typename T> il void chkmin(T &x, T y) {x = min(x, y);}
template <typename T> il void chkmax(T &x, T y) {x = max(x, y);}
bool Beg;
namespace My_Space {
struct IO {
    static const int Size = (1 << 21);
    char buf[Size], *p1, *p2; int st[105], Top;
    ~IO() {clear();}
    il void clear() {fwrite(buf, 1, Top, stdout); Top = 0;}
    il char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Size, stdin), p1 == p2) ? EOF : *p1++;}
    il void pc(const char c) {Top == Size && (clear(), 0); buf[Top++] = c;}
    il IO &operator >> (char &c) {while(c = gc(), c == ' ' || c == '\n' || c == '\r'); return *this;}
    template <typename T> il IO &operator >> (T &x) {
        x = 0; bool f = 0; char ch = gc();
        while(!isdigit(ch)) {if(ch == '-') f = 1; ch = gc();}
        while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
        f ? x = -x : 0; return *this;
    }
    il IO &operator << (const char c) {pc(c); return *this;}
    template <typename T> il IO &operator << (T x) {
        if(x < 0) pc('-'), x = -x;
        do st[++st[0]] = x % 10, x /= 10; while(x);
        while(st[0]) pc('0' + st[st[0]--]);
        return *this;
    }
    il IO &operator << (const char *s) {for(int i = 0; s[i]; i++) pc(s[i]); return *this;}
}fin, fout;

int n, m, rt;
int head[N], edgenum;
struct node {
    int nxt, to;
}edge[N << 1];
il void add(int u, int v) {
    edge[++edgenum] = {head[u], v}; head[u] = edgenum;
    edge[++edgenum] = {head[v], u}; head[v] = edgenum;
}

int siz[N], son[N], top[N], dfn[N], idx, fa[N];
il void dfs1(int x, int fth) {
    siz[x] = 1; fa[x] = fth;
    dfn[x] = ++idx;
    for(int i = head[x]; i; i = edge[i].nxt) {
        int to = edge[i].to;
        if(to == fth) continue;
        dfs1(to, x);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
    }
}

int ga[N][5], dep[N];
il void dfs2(int x, int rt) {
    top[x] = rt;
    if(x == rt) {
        ga[x][0] = top[fa[x]]; dep[x] = dep[top[fa[x]]] + 1;
        for(int i = 1; i <= 4; i++) ga[x][i] = ga[ga[x][i - 1]][i - 1];
    }
    if(son[x]) dfs2(son[x], rt);
    for(int i = head[x]; i; i = edge[i].nxt) {
        int to = edge[i].to;
        if(to == fa[x] || to == son[x]) continue;
        dfs2(to, to);
    }
}

il int LCA(int u, int v) {
    int x = top[u], y = top[v];
    if(x == y) return dfn[u] < dfn[v] ? u : v;
    if(dep[x] > dep[y]) swap(x, y), swap(u, v);
    for(int i = 4; i >= 0; i--) {
        if(dep[ga[y][i]] > dep[x]) y = ga[y][i];
    }
    if(ga[y][0] == x) return dfn[fa[y]] < dfn[u] ? fa[y] : u;
    if(dep[x] != dep[y]) y = ga[y][0];
    for(int i = 4; i >= 0; i--) {
        if(ga[x][i] != ga[y][i]) x = ga[x][i], y = ga[y][i];
    }
    x = fa[x], y = fa[y];
    return dfn[x] < dfn[y] ? x : y;
}

il void main() {
    fin >> n >> m >> rt;
    for(int i = 1; i < n; i++) {
        int u, v; fin >> u >> v;
        add(u, v);
    }
    dfs1(rt, 0); dfs2(rt, rt);
    while(m--) {
        int u, v;
        fin >> u >> v;
        fout << LCA(u, v) << '\n';
    }
}
}
il void File() {freopen(".in", "r", stdin); freopen(".out", "w", stdout);}
bool End;
il void Usd() {cerr << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
int main() {
    My_Space::main();
    Usd();
    return 0;
}