LCA倍增算法

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100010;
const int LOG = 20;
vector<int> adj[MAXN];
int fa[LOG][MAXN];
int depth[MAXN];
int n;
void bfs(int root) {
    memset(fa, -1, sizeof(fa)); 
    queue<int> q;
    q.push(root);
    depth[root] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (v != fa[0][u]) { 
                depth[v] = depth[u] + 1;
                fa[0][v] = u; 
                q.push(v);
            }
        }
    }
    for (int k = 1; k < LOG; k++) {
        for (int u = 1; u <= n; u++) {
            if (fa[k-1][u] != -1) {
                fa[k][u] = fa[k-1][ fa[k-1][u] ];
            }
        }
    }
}
int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = LOG-1; k >= 0; k--) {
        if (fa[k][u] != -1 && depth[ fa[k][u] ] >= depth[v]) {
            u = fa[k][u];
        }
    }
    if (u == v) return u; 
    for (int k = LOG-1; k >= 0; k--) {
        if (fa[k][u] != -1 && fa[k][u] != fa[k][v]) {
            u = fa[k][u];
            v = fa[k][v];
        }
    }
    return fa[0][u]; 
}
int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs(1);
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << "LCA(" << u << "," << v << ") = " << lca(u, v) << endl;
    }
    return 0;
}