倍增lca

【模板】最近公共祖先（LCA） - 洛谷

这道题就是板子题，www，写的时候出了些问题，困扰了好久

#include 
#include 
using namespace std;
 
const int N = 5e5 + 10;
int n, m, root;
vector<int> g[N]; //邻接表存图
int deep[N], fa[N][20]; // deep存深度， fa[i][j] 存i向上跳2^j个单位
 
void dfs(int u, int pre) { // dfs初始化一下深度和各节点祖先
    deep[u] = deep[pre] + 1;
    for (int i = 1; i <= 19; i ++ )
        fa[u][i] = fa[fa[u][i - 1]][i - 1]; //倍增,类似st表初始化
    for (int i = 0; i < g[u].size(); i++)
    {
        int j = g[u][i];
        if (j == pre) continue; // 除了父节点以外更新所有u相连的节点, 将父节点设置一下
        fa[j][0] = u;
        dfs(j, u);
    }
}
 
//lca就是先统一深度，然后一起向上跳，直到达到同一祖先 //即为最近公共祖先
int lca(int x, int y) {
    if(deep[x] < deep[y]) //x设为深度更大的那个点
        swap(x, y);
 
    for (int i = 19; i >= 0; i -- ) {
        if(deep[fa[x][i]] >= deep[y]) //这里要有等号,跳到同一深度
            x = fa[x][i];
    }
    if(x == y) // 这里说明y就是x的祖先
        return x;
    for (int i = 19; i >= 0; i -- ) { //一起向上跳
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0]; //返回祖先
}
 
int main() {
    cin >> n >> m >> root;
 
    for (int i = 1; i < n; i ++ ) {
        int a, b;
        cin >> a >> b;
 
        g[a].push_back(b);
        g[b].push_back(a);
    }
 
    dfs(root, root);
 
    for (int i = 1; i <= m; i ++ ) {
        int a, b;
        cin >> a >> b;
 
        cout << lca(a, b) << endl;
    }
 
    return 0;
}