0分求调,悬关
查看原帖
0分求调,悬关
960206
topcsa楼主2024/10/9 21:38
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int dep[N];
int n, q;
int vis[N];
int f[N][20];
int mx[N];
vector<int> g[N];
void dfs(int u, int fa, int maxn) {
	if (u > maxn) {
		maxn = u;
	}
	mx[u] = maxn;
	dep[u] = dep[fa] + 1;
	vis[u] = 1;
	f[u][0] = fa;
	for (auto v : g[u]) {
		if (!vis[v] && v != fa) {
			dfs(v, u, maxn);
		}
	} 
}
int lca(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int i = 19; i >= 0; i--) {
		if (dep[u] - (1 << i) >= dep[v]) {
			u = f[u][i];
		}
	}
	if (u == v) {
		return u;
	}
	for (int i = 19; i >= 0; i--) {
		if (f[u][i] != f[v][i]) {
			u = f[u][i];
			v = f[v][i];
		}
	}
	return f[u][0];
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		int x;
		cin >> x;
		g[x].push_back(i);
	}
	dfs(0, 0, 0);
	cin >> q;
	while (q--) {
		int fa, m;
		cin >> m >> fa;
		for (int i = 1; i < m; i++) {
			int x;
			cin >> x;
			fa = lca(fa, x);
		} 
		cout << mx[fa] << '\n';
	}
	return 0;
}

2024/10/9 21:38
加载中...