@[liaoxingrui](/user/744895) 你确定不是CE?
by FEEL_HARD_CYT @ 2024-03-29 16:51:58
@[FEEL_HARD_CYT](/user/744853) c++98
by liaoxingrui @ 2024-03-29 16:53:02
6
by FEEL_HARD_CYT @ 2024-03-29 16:57:03
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,x,tot,cnt;
int p;
int fa[N],dep[N],siz[N],son[N],dfn[N],top[N],head[N];
struct node{
int xx,yy;
}next[N<<1];
inline void add(int x,int y){
tot++;
next[tot].xx=y;
next[tot].yy=head[x];
head[x]=tot;
}
inline void dfs1(int node){
siz[node]=1;
int ma=0;
for(int i=head[node];i;i=next[i].yy){
int w=next[i].xx;
if(w!=fa[node]){
fa[w]=node;
dep[w]=dep[node]+1;
dfs1(w);
siz[node]+=siz[w];
if(siz[w]>ma){
son[node]=w;
ma=siz[w];
}
}
}
}
inline void dfs2(int node,int t){
if(dfn[node])return;
dfn[node]=++cnt;
top[node]=t;
for(int i=head[node];i;i=next[i].yy){
int w=next[i].xx;
if(w!=fa[node]&&w!=son[node])
dfs2(w,w);
if(w==son[node]) dfs2(w,t);
}
}
inline int Lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
x=fa[top[x]];
}
return (dep[x]<dep[y]?x:y);
}
int main(){
ios::sync_with_stdio(0);
ios_base::sync_with_stdio(0);
cin.tie(NULL),cout.tie(NULL);
cin>>n;
for(int i=1;i<n;i++){
cin>>x;
add(x,i);
add(i,x);
}
dfs1(0);
dfs2(0,0);
cin>>m;
int ans = 0;
while(m--){
cin>>n;
ans = p;
n--;
cin>>x;
ans = x;
while(n--) {
cin>>x;
ans = Lca(x,ans);
}
int anss = 0;
while(ans) {
anss = max(anss,ans);
ans = fa[ans];
}
cout<<anss<<"\n";
}
return 0;
}
```
AC注意求的是路上的编号的最大值
by FEEL_HARD_CYT @ 2024-03-29 17:22:17
@[liaoxingrui](/user/744895)
by FEEL_HARD_CYT @ 2024-03-29 17:22:28