50分求调
查看原帖
50分求调
1022974
Ryan_L_F楼主2025/6/20 13:22

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = log(N) + 11;
int f[N][M], n, T, dep[N], Max[N];
vector <int> tr[N];

void dfs(int x, int fa){
	for(int i = 1; i <= M - 10; i++)
		f[x][i] = f[f[x][i - 1]][i - 1];
	
	for(auto y : tr[x]){
		if(y == fa) continue;
		
		dep[y] = dep[x] + 1;
		f[y][0] = x;
		dfs(y, x);
	}
}

void dfs(int x, int fa, int maxn){
	for(auto y : tr[x]){
		if(y == fa) continue;
		
		int new_maxn = max(maxn, y);
		Max[y] = new_maxn;
		dfs(y, x, new_maxn);
	}
}

int lca(int x, int y){
	if(dep[x] < dep[y]) 
		swap(x, y);
	
	for(int i = M - 10; i >= 0; i--)
		if(dep[f[x][i]] >= dep[y])
			x = f[x][i];
	
	if(x == y)
		return x;
		
	for(int i = M - 10; i >= 0; i--)
		if(f[x][i] != f[y][i]){
			x = f[x][i];
			y = f[y][i];
		}
	
	return f[x][0];
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < n; i++){
		int j; scanf("%d", &j);
		
		tr[i].push_back(j);
		tr[j].push_back(i);
	}
	
	dep[0] = 1;
	dfs(0, -1);
	Max[0] = 0;
	dfs(0, -1, 0);
	scanf("%d", &T);
	
	while(T --){
		int m, ans; scanf("%d %d", &m, &ans);
		m --;
		
		while(m --){
			int x; scanf("%d", &x);
			ans = lca(ans, x);
		}
		
		printf("%d\n", Max[ans]);
	}
	return 0;
} 
2025/6/20 13:22
加载中...