1 solutions
-
0
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