树链剖分

cpp
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int M=5e5+5;
vector<int>f[M];
int dep[M],son[M],fa[M],sz[M],top[M];

void dfs1(int now,int t) {
    dep[now]=dep[t]+1;
    sz[now]=1;
    fa[now]=t;
    for(auto x:f[now]) {
        if(x==t)continue;
        dfs1(x,now);
        sz[now]+=sz[x];
        if(sz[x]>sz[son[now]]) son[now]=x;
    }
}
void dfs2(int now,int t) {
    top[now]=t;
    if(son[now])dfs2(son[now],t);
    for(auto x:f[now]) {
        if(x==son[now]||x==fa[now])continue;
        dfs2(x,x);
    }
}
int lca(int x,int y) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
void solve() {
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<n;++i) {
        int x,y;
        cin>>x>>y;
        f[x].push_back(y);
        f[y].push_back(x);
    }
    dfs1(s,s);
    dfs2(s,s);
    while (m--) {
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<"\n";
    }
}

signed  main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    solve();

    return 0;
}

倍增

cpp
#include <bits/stdc++.h>
using namespace std;
// #define int long long

const int M = 1e6 + 5;
int fa[M][22], dep[M];
vector<int> f[M];
inline void dfs(int x, int t)
{
    fa[x][0] = t;
    dep[x] = dep[t] + 1;
    for (auto to : f[x])
        if (to != t)
            dfs(to, x);
} // 求 fa[i][0]
inline int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[fa[x][i]] >= dep[y])
            x = fa[x][i];
    }
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
    {
        if (fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
} // 求两个节点的 LCA
void solve()
{
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        f[x].push_back(y);
        f[y].push_back(x);
    }
    dfs(s, 0);
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << "\n";
    }
}
int main()
{
    ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
        solve();

    return 0;
}