为什么我的LCA出现了负数【求条玄关】
查看原帖
为什么我的LCA出现了负数【求条玄关】
1284815
canwen楼主2025/7/31 18:17

刚刚看了思路和题解一样的,莫名其妙只对了前 25%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;
}
2025/7/31 18:17
加载中...