求60分改正
查看原帖
求60分改正
737737
collin楼主2024/7/3 20:49
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N][20],n,q,d[N],m,a[N];
vector<int> g[N];
void dfs(int u,int fa,int dep){
    d[u]=dep;
    f[u][0]=fa;
    for(int i=1;i<=18;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int v:g[u]){
        if(v==fa)
            continue;
        dfs(v,u,dep+1);
    }
}
int lca(int x,int y){
    if(d[x]<d[y])
        swap(x,y);
    for(int i=18;i>=0;i--){
        if(d[f[x][i]]>=d[y])
            x=f[x][i];
    }
    if(x==y)
        return x;
    for(int i=18;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    cin>>n;
    int u;
    for(int i=1;i<n;i++){
        cin>>u;
        g[i].push_back(u);
        g[u].push_back(i);
    } 
    dfs(0,-1,1);
    cin>>q;
    while(q--){
        cin>>m;
        for(int i=1;i<=m;i++)
            cin>>a[i];
        int ans=a[1];
        for(int i=2;i<=m;i++)
            ans=lca(ans,a[i]);
        int maxx=ans;
        u=ans;
        while(f[u][0]!=-1){
            maxx=max(maxx,f[u][0]);
            u=f[u][0];
        }
        cout<<maxx<<'\n';
    }
    
    return 0;
}

这段程序哪里有问题了,60分,请大佬指点,谢谢

2024/7/3 20:49
加载中...