1 solutions

  • 0
    @ 2024-12-5 18:19:40

    C++ :

    #include<bits/stdc++.h>
    using namespace std;
    
    int n,q,m;
    int fa[100003][30];
    int mx[100003],dep[100003];
    int l2[100003];
    vector<int>edg[100003];
    
    void dfs(int x,int f,int mxn){
    	if(x>mxn)mxn=x;
    	mx[x]=mxn;  dep[x]=dep[f]+1;//预处理前缀最大值和深度
    	if(x!=0){
    		fa[x][0]=f;
    		for(int i=1;i<=l2[dep[x]];i++)
    			fa[x][i]=fa[fa[x][i-1]][i-1];//预处理2^i级祖先
    	}
    	for(int i=0;i<edg[x].size();i++)
    		dfs(edg[x][i],x,mxn);//向下递归
    }
    
    int lca(int a,int b){
    	if(dep[a]<dep[b])swap(a,b);
    	while(dep[a]>dep[b]){//调平深度
    		a=fa[a][l2[dep[a]-dep[b]]];
    	}
    	if(a==b)return a;//特判
    	for(int i=l2[dep[a]];i>=0;i--){//求祖先
    		if(fa[a][i]!=fa[b][i]){
    			a=fa[a][i];
    			b=fa[b][i];
    		}
    	}
    	return fa[a][0];
    }
    
    int main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);cout.tie(0);
    	cin>>n;
    	l2[0]=-1;
    	for(int i=1;i<n;i++){
    		l2[i]=l2[i>>1]+1;//预处理对数
    		int f;  cin>>f;
    		edg[f].push_back(i);//连边
    	}
    	dfs(0,0,0);
    	cin>>q;
    	while(q--){
    		int F,x;
    		cin>>m>>F;
    		while(--m){
    			cin>>x;
    			F=lca(F,x);
    		}
    		cout<<mx[F]<<'\n';
    	}
    	return 0;
    }
    
    • 1

    Information

    ID
    9176
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By