最近公共祖先

柿子饼同学

代码不知道问题出在哪 , 总是输出 0
求指出
题目:https://www.luogu.com.cn/problem/P3379

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
 //   ST表    深度数组 log2(n)存储
int dp[N][21], dep[N], lg[N];
int n, m, s;
vector<int> tree[N]; // 邻接表存储

void dfs(int x, int p){//x当前节点 , p是x的父母
    dep[x] = dep[p] + 1;
    dp[x][0] = p;
    for(int i = 1; (1<<i)<= dep[x]; i++){
        dp[x][i] = dp[dp[x][i-1]][i-1];
    }
    for(auto i : tree[x]){
        if(i != p) dfs(i, x);
    }
}

int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = lg[dep[x]]; i >= 0; i--){
        if((1<<i)+dep[x] >= dep[y]){
            x = dp[x][i];
        }
    }
    if(x == y) return y;
    for(int i = lg[dep[x]]; i >= 0; i--){
        if(dp[x][i] != dp[y][i]){
            x = dp[x][i];
            y = dp[y][i];
        }
    }
    return dp[x][0];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int x, y;
    cin >> n >> m >> s;
    for(int i = 1; i <= n; i++){//预处理log2(n)
        lg[i] = lg[i-1] + ((1<<lg[i-1])==i);
    }
    for(int i = 1; i < n; i++){
        cin >> x >> y;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    dfs(s, s);

    while(m--){
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }

    return 0;
}

谢谢大家了

jhq999

看看，没看明白
只能自己写一个还没通过

void huisu(int* a,int n,int pt1,int pt2)
{
    if(pt1==a[0]||pt2==a[0])printf("%d\n",a[0]);
    else
    {
        int i=0,j=0,pt3=pt1,pt4=pt2;
        while(pt3!=a[0])pt3=a[pt3],i++;//////计算到根节点的深度
        while(pt4!=a[0])pt4=a[pt4],j++;//////计算到根节点的深度
        pt3=pt1,pt4=pt2;
        while(1)////////跑到相同的深度
        {
            if(i==j)break;
            i>j?(pt3=a[pt3],i--):(pt4=a[pt4],j--);
        }
        while(pt3!=pt4)////////假如相同深度的值相同就是共同祖先
        {
            pt3=a[pt3],pt4=a[pt4];
        }
        printf("%d\n",pt3);
    }

}
int main()
{

    int n=0,m=0,s=0,i=0,id=0,parent=0;
    scanf("%d%d%d",&n,&m,&s);
    int* a=(int*)calloc(n+1,sizeof(int));
    int (*b)[2]=(int (*)[2])calloc(m*2,sizeof(int));
    a[0]=s;
    for(i=0;i<n-1;i++)
    {
        scanf("%d%d",&id,&parent);
        a[id]=parent;/////每个节点存储的是父节点下标
    }
    for(i=0;i<m;i++)
    {
        scanf("%d%d",b[i],b[i]+1);
    }
    for(i=0;i<m;i++)
    {

        huisu(a,n,b[i][0],b[i][1]);
    }
    free(b);
    free(a);

    return 0;
}

柿子饼同学

jhq999 发表于 2022-7-14 18:14
看看，没看明白
只能自己写一个还没通过

唔 , 这个可能没有用 ST 表那么快