社区讨论
0pts,样例过了,求调
P10113[GESP202312 八级] 大量的工作沟通参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mm1zo0nv
- 此快照首次捕获于
- 2026/02/25 20:06 2 周前
- 此快照最后确认于
- 2026/02/27 10:10 2 周前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,f,q,fa[100005][35],dep[100005];
vector<int> g[100005];
void build(int x,int fatt){
fa[x][0]=fatt;
dep[x]=dep[fatt]+1;
for(int i=1;i<=20;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=0;i<g[x].size();i++){
build(g[x][i],x);
}
}
int lca(int x,int y){
if(dep[y]>dep[x])swap(x,y);
for(int i=20;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]){
x=fa[x][i];
}
}
if(x==y)return x;
for(int i=19;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d",&f);
g[f].push_back(i);
}build(0,0);
scanf("%d",&q);
while(q--){
int m,x,y;
scanf("%d%d",&m,&x);
for(int i=1;i<m;i++){
scanf("%d",&y);
x=lca(x,y);
}
int maxx=x,t=x;
while(t){
t=fa[t][0];
if(t>maxx)maxx=t;
}
printf("%d\n",maxx);
}
return 0;
}
必关
回复
共 2 条回复,欢迎继续交流。
正在加载回复...