刚刚看了思路和题解一样的,莫名其妙只对了前 25% 个点。
然后看到出现了 -
。
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define int long long
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
#define pc putchar
int in(){
char a=getchar();int k=0,kk=1;
while(!(a>='0'&&a<='9')) {if(a == '-') kk = -1;a = getchar();}
while(a>='0'&&a<='9') k = k*10 + a - '0', a = getchar();
return k*kk;
}
void out(int a){
if(a < 0) pc('-'), a= -a;
if(a > 9) out(a/10);
pc('0'+a%10);
}
#define fst first
#define snd second
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rrep(i,a,b) for(int i=(a);i>=(b);--i)
#define _reps(i,a,b,c) for(int i=(a);i<=(b);c)
#define _rreps(i,a,b,c) for(int i=(a);i>=(b);c)
#define _graph(i) for(int i=head[u];i;i=e[i].nxt)
#define mp make_pair
#define pint pair<int,int>
#define i128 __int128
#define i64 long long
#define pb emplace_back
#define FRR(file) freopen(file,"r",stdin)
#define FRW(file) freopen(file,"w",stdout)
#define nowtime (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 5;
int n,head[N],tot;
struct node{
int nxt,v;
}e[2*N];
void add(int u,int v){
e[++tot].v = v, e[tot].nxt = head[u], head[u] = tot;
}
int ff[N],f[N][20];
void dfs(int u,int fa,int maxn){
maxn = max(maxn,u);
ff[u] = maxn;
_graph(i){
int v = e[i].v;
if(v != fa) dfs(v,u,maxn);
}
}
int dep[N],lg[N];
void dfs1(int u,int fa){
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for(int i=1;i<=lg[dep[u]];++i){
f[u][i] = f[f[u][i-1]][i-1];
}
_graph(i){
int v = e[i].v;
if(v != fa) dfs1(v,u);
}
}
int LCA(int x,int y){
if(dep[x] < dep[y]) swap(x,y);
while(dep[x] > dep[y]){
x = f[x][lg[dep[x]-dep[y]]-1];
}
if(x == y) return x;
if(dep[x] > dep[y]) swap(x,y);
for(int i=dep[x]-1;i>=0;--i){
if(f[x][i] != f[y][i]){
x = f[x][i], y = f[y][i];
}
}
return f[x][0];
}
signed main(){
n = in();
_rep(i,1,n) lg[i] = lg[i>>1] + 1;
_rep(i,2,n){
int x = in();++x;
add(x,i), add(i,x);
}
dfs(1,0,0);
dfs1(1,0);
int Q = in();
while(Q--){
int m = in(), u;
int x = in(), y = in();
x++,y++;
u = LCA(x,y);
m -= 2;
_rep(i,1,m){
x = in(),++x;
u = LCA(u,x);
}
u = ff[u];
out(u-1), pc('\n');
}
return 0;
}