萌新，新学图论，有低级错误望见谅 代码

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

const int N = 1e6 + 10;
int n, m, vis[N], ans, mu, mv, sn = 1, t, s, dep[N], vis2[N], fa[N][20];
int log_2[N];

struct edge {
    int u, v, id;
    int nxt;
}a[N];
int cnt, hd[N], cnt2 = 1;

void addedge(int u, int v) {
    a[++cnt].u = u;
    a[cnt].v = v;
    a[cnt].nxt = hd[u];
    hd[u] = cnt;
}

int nc;

void dfs(int f, int son) {
    dep[son] = dep[f] + 1, fa[son][0] = f;
    for (int j = 1; j <= log_2[dep[son]]; j++) {
        fa[son][j] = fa[fa[son][j - 1]][j - 1];
    }
    for (int i = hd[son]; i; i = a[i].nxt) {
        if (a[i].v == f) continue;
        dfs(son, a[i].v);
    }
}

void lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);

    if (dep[x] > dep[y]) x = fa[x][log_2[dep[x] - dep[y]]];
    //cout << dep[x] << ':' << dep[y] << endl;
    if (x == y) {
        cout << x << "\n";
        return;
    }
    for (int i = log_2[dep[x]] - 1; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    cout << fa[x][0] << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    cin >> n >> m >> s;
    log_2[0] = -1;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        addedge(x, y);
        addedge(y, x);
        log_2[i] = log_2[i / 2] + 1;
    }
    dfs(0, s);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        lca(x, y);
    }
    return 0;
}

记录