倍增

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 50;

int n, m, s;
int head[N], tot;
int lg[N]; // log2(i)+1
int fa[N][22], dep[N];
struct Edge {
    int nex, to;
}eg[N << 1];
void add(int a, int b) {
    eg[++tot] = (Edge){head[a], b};
    head[a] = tot;
}
void init() {
    for(int i = 1; i <= n; i++) {
        lg[i] = lg[i-1] + ((1 << lg[i-1]) == i);
    }
}
void dfs(int u, int F) {
    dep[u] = dep[F] + 1;
    fa[u][0] = F;
    for(int i = 1; i <= lg[dep[u]]; i++) {
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for(int i = head[u]; i; i = eg[i].nex) {
        int to = eg[i].to;
        if(to != F) dfs(to, u);
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = fa[x][lg[dep[x]-dep[y]] - 1];
    if (x == y) return x;
    for (int i = lg[dep[x]] - 1; i >= 0; i--) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i]; y = fa[y][i];
        }
    }
    return fa[x][0];
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1, a, b; i < n; i++) {
        scanf("%d%d", &a, &b);
        add(a, b); add(b, a);
    }
    init(); dfs(s, 0);
    for(int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

树链剖分

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 50;
int n, m, s;

int head[N], tot;
struct Edge {
    int nex, to;
}e[N << 1];
void add(int a, int b) {
    e[++tot] = (Edge){head[a], b};
    head[a] = tot;
}

struct Node {
    int dep, fa, sz;
    int mson, top;
}nd[N];
void dfs1(int rt, int fa, int dep) {
    nd[rt].dep = dep; nd[rt].fa = fa; nd[rt].sz = 1;
    int mson = -1;
    for (int i = head[rt]; i; i = e[i].nex) {
        int to = e[i].to;
        if (to == fa) continue;
        dfs1(to, rt, dep + 1);
        nd[rt].sz += nd[to].sz;
        if (nd[to].sz > mson) {
            mson = nd[to].sz;
            nd[rt].mson = to;
        }
    }
}
void dfs2(int rt, int tp) {
    nd[rt].top = tp;
    if (!nd[rt].mson) return;
    dfs2(nd[rt].mson, tp);
    for (int i = head[rt]; i; i = e[i].nex) {
        int to = e[i].to;
        if (to == nd[rt].fa || to == nd[rt].mson) continue;
        dfs2(to, to);
    }
}

#define topx nd[x].top
#define topy nd[y].top
int lca(int x, int y) {
    while (topx != topy) {
        if(nd[topx].dep < nd[topy].dep) y = nd[topy].fa;
        else x = nd[topx].fa;
    }
    return nd[x].dep < nd[y].dep ? x : y;
}

int main(int argc, const char * argv[]) {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1, a, b; i < n; i++) {
        scanf("%d%d", &a, &b);
        add(a, b); add(b, a);
    }
    dfs1(s, 0, 1); dfs2(s, s);
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

例题： 洛谷P3292 [SCOI2016]幸运数字