题解

此代码来源于用户“Hyperion_1210”
100%正确

#include<bits/stdc++.h>
using namespace std;
const int N = 1E5 + 10;
int n;
vector<int> g[N];
int dep[N], fat[N][25];

void dfs(int now, int fa) {
	fat[now][0] = fa;
	dep[now] = dep[fa] + 1;

	for (int i = 1; i <= 20; i++) {
		fat[now][i] = fat[fat[now][i - 1]][i - 1];
	}

	for (auto v : g[now]) {
		dfs(v, now);
	}

}

int LCA(int x, int y) {
	//1、先跳到同一层
	if (dep[x] < dep[y]) swap(x, y);
	int dis = dep[x] - dep[y];
	for (int i = 0; i <= 20; i++) {
		if (dis >> i & 1) x = fat[x][i];
	}

	if (x == y) return x;

	//2、一起跳到LCA的下一层
	for (int i = 20; i >= 0; i--) {
		if (fat[x][i] != fat[y][i]) {
			x = fat[x][i], y = fat[y][i];
		}
	}

	return fat[x][0];
}

int main(){
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		int t;
		cin >> t;
		g[t].push_back(i);
	}

	dfs(0, 0);

	int q;
	cin >> q;
	while (q--) {
		int m, id[10005] = { 0 };
		cin >> m;
		for (int i = 1; i <= m; i++) cin >> id[i];
		int pos = id[1];
		for (int i = 2; i <= m; i++) {
			pos = LCA(pos, id[i]);
		}
		cout << pos << endl;
	}


	return 0;
}