hack数据怎么过,求
查看原帖
hack数据怎么过,求
902912
Yang_Ziyue楼主2024/11/30 08:21
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
#define fi first
#define se second
#define ts cout << "tt" << endl;
#define bl << ' ' <<
#define MX 1005
#define zr(x) memset(x, 0, sizeof x)
#define mmx(x) memset(x, 0x3f, sizeof x)
#define fu1(x) memset(x, -1, sizeof x)
#define mmn(x) memset(x, -0x3f, sizeof x)
#define el << endl
#define hfmx 0x3f3f3f3f3f3f3f3f / 2
#define sf(x) for(register int i = 1 ; i <= x ; i++)
#define frer(x) freopen(x, "r", stdin)
#define frew(x) freopen(x, "w", stdout)
#define pii pair<int, int>
int deep[100005];
int dp[100005][18];
vector<int> g[100005];
vector<int> tv;
int n, q, t1, m;
void pres(int fa, int x, int d) {
	deep[x] = d;
	dp[x][0] = fa;
	for (int i : g[x]) {
		if (i != fa) {
			pres(x, i, d + 1);
		}
	}
}
int query(int x, int y) {
	if (x == y) return x;
	if (deep[x] < deep[y]) swap(x, y);
	for (int i = 17 ; i >= 0 ; i--) {
		if (deep[dp[x][i]] >= deep[y]) {
			x = dp[x][i];
		}
	}
	if (x == y) return x;
	for (int i = 17 ; i >= 0 ; i--) {
		if (dp[x][i] != dp[y][i]) {
			x = dp[x][i];
			y = dp[y][i];
		}
	}
	return dp[x][0];
}
signed main() {
	cin >> n;
	for (int i = 1 ; i <= n - 1 ; i++) {
		cin >> t1;
		g[t1].push_back(i);
	}
	pres(-1, 0, 1);
	dp[0][0] = 0;
	for (int i = 1 ; i <= 17 ; i++) {
		for (int j = 1 ; j <= n ; j++) {
			dp[j][i] = dp[dp[j][i - 1]][i - 1];
		}
	}
	cin >> q;
	while (q--) {
		cin >> m;
		for (int i = 1 ; i <= m ; i++) {
			cin >> t1;
			tv.push_back(t1);
		}
		int rt = query(tv[0], tv[1]);
		for (int i = 2 ; i < tv.size() ; i++) {
			if (rt == 0) break;
			rt = query(rt, tv[i]);
		}
		cout << rt << endl;
		tv.clear();
	}
	return 0;
}

2024/11/30 08:21
加载中...