LCA 模板（非原创）

离线版本

struct Edge{
    int v, c;
};
vector<Edge> G[maxn], qur[maxn];
int fa[maxn], dis[maxn], n, ans[205];
bool vis[maxn];
 
int Find(int x) {
    return fa[x] = fa[x] == x ? x : Find(fa[x]);
}
 
void init() {
    for (int i = 1; i <= n; i++) G[i].clear(), qur[i].clear(), fa[i] = i;
    dis[1] = 0; memset(vis, 0, sizeof(vis));
}
 
void Tanjar_LCA(int x) {
    vis[x] = 1;
    for (int i = 0; i < G[x].size(); i++) {
        int hh = G[x][i].c, u = G[x][i].v;
        if (vis[u]) continue;
        dis[u] = dis[x] + hh;
        Tanjar_LCA(u);
        fa[u] = Find(x);
    }
    for (int i = 0; i < qur[x].size(); i++) {
        int u = qur[x][i].v;
        if (!vis[u]) continue;
        int lca = Find(u);
        ans[qur[x][i].c] = dis[x] + dis[u] - 2*dis[lca];
    }
}

在线版本

vector<int> G[maxn];
int ver[maxn*2], dp[maxn*2][33], tot, R[maxn*2], vis[maxn], first[maxn];
int n;
 
void dfs(int x, int dep) {
    vis[x] = 1, ver[++tot] = x; R[tot] = dep; first[x] = tot;
    for (int i = 0; i < G[x].size(); i++) {
        int u = G[x][i];
        if (vis[u]) continue;
        dfs(u, dep+1);
        ver[++tot] = x; R[tot] = dep;
    }
}
 
void RMQ_init(int len) {
    for (int i = 1; i <= len; i++) dp[i][0] = i;
    for (int j = 1; (1<<j) <= len; j++) {
        for (int i = 1; i + (1 << j) - 1 <= len; i++) {
            int a = dp[i][j-1], b = dp[i+(1<<(j-1))][j-1];
            dp[i][j] = R[a] < R[b] ? a : b;
        }
    }
}
 
int RMQ(int l, int r) {
    int k = 0;
    while ((1 << (k+1)) <= r-l+1) k++;
    int a = dp[l][k], b = dp[r-(1<<k)+1][k];
    return R[a] < R[b] ? a : b;
}
 
int LCA(int u, int v) {
    int x = first[u], y = first[v];
    if (x > y) swap(x, y);
    return ver[RMQ(x, y)];
}
 
void init() {
    tot = 0;
    for (int i = 1; i <= n; i++) G[i].clear();
    memset(vis, 0, sizeof(vis));
}
 
 
void solve() {
    int m;
    cin >> n >> m;
    init();
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    dfs(1, 1);
    RMQ_init(tot);
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        int x = LCA(u, v);
        cout << x << endl;
    }
}