1 条题解

  • 1
    @ 2024-6-2 11:07:30
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N=200005;
    int n,m,k,s,t,Q,f[N][21],de[N],d[N],mx[N];
    queue<int> q;
    vector<int> e[N];
    void dfs(int u){
    	for (int v:e[u]){
    		if (v!=f[u][0]){
    			f[v][0]=u;
    			de[v]=de[u]+1;
    			mx[v]=max(v,mx[u]);
    			dfs(v);
    		}
    	}
    }
    int lca(int u,int v){
    	if (de[u]<de[v]) swap(u,v);
    	for (int k=de[u]-de[v],o=0;k;k>>=1,++o)
    		if (k&1) u=f[u][o];
    	if (u==v) return u;
    	for (int j=20;j>=0;--j)
    		if (f[u][j]!=f[v][j])
    			u=f[u][j],v=f[v][j];
    	return f[u][0];
    }
    int main(){
    	freopen("in.txt","r",stdin);
    	cin>>n;
    	for (int i=2;i<=n;++i){
    		cin>>s;s++;
    		e[s].push_back(i);
    	}
    	mx[1]=1;
    	dfs(1);
    	for (int j=1;j<=20;++j)
    		for (int i=1;i<=n;++i)
    			f[i][j]=f[f[i][j-1]][j-1];
    	cin>>Q;
    	int u,v;
    	while (Q--){
    		cin>>k;
    		int p;
    		for (int i=1;i<=k;++i){
    			cin>>s;s++;
    			if (i==1) p=s;
    			else p=lca(p,s);
    		}
    		cout<<mx[p]-1<<"\n";
    	}
    }
    
    
    • 1

    信息

    ID
    788
    时间
    2000ms
    内存
    500MiB
    难度
    10
    标签
    递交数
    7
    已通过
    0
    上传者