倍增LCA求条
查看原帖
倍增LCA求条
1318015
Linda0417楼主2025/7/3 21:29

全输出的是0

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, q, root, x, y, father[N][25], dep[N];
vector<int> g[N]; 
void dfs(int x) {
    if(father[x][0] == 0) dep[x] = 1;
    else dep[x] = dep[father[x][0]] + 1;
    for(int i = 0; i < g[x].size(); i++) {
        int v = g[x][i];
        if(v != father[x][0]) dfs(v); 
    } 
}
int LCA(int x, int y) { 
    if(dep[x] < dep[y]) swap(x, y); 
    for(int i = 22; i >= 0; i--) {
        if(dep[father[x][i]] >= dep[y]) x = father[x][i]; 
    }
    if(x == y) return x;  
    for(int i = 22; i >= 0; i--) { 
        if(father[x][i] != father[y][i]) { 
            x = father[x][i]; 
            y = father[y][i]; 
        } 
    }  
    return father[x][0]; 
} 
int main() { 
    scanf("%d %d %d", &n, &q, &root); 
    for(int i = 1; i < n; i++) { 
        scanf("%d %d", &x, &y);
        g[x].push_back(y); 
        father[y][0] = x; 
    } 
    dfs(root); 
    for(int j = 1; (1 << j) <= n; j++) 
        for(int i = 1; i <= n; i++) 
            father[i][j] = father[father[i][j - 1]][j - 1]; 
    
    while(q--) { 
        scanf("%d %d", &x, &y); 
        printf("%d\n",LCA(x, y)); 
    } 
    return 0; 
}
2025/7/3 21:29
加载中...