WA 0 pts 求调,样例都过了
查看原帖
WA 0 pts 求调,样例都过了
842408
pangyuchen75楼主2024/6/12 12:01

CodeCode :

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e6 + 5;

int n, q, m;
int u, v;
int tot;
int head[N];
int depth[N];
int anc[N][16];

struct Edge {
	int to;
	int next;
};

Edge edge[N];

void add(int u, int v) {
	tot ++ ;
	edge[tot].to = v;
	edge[tot].next = head[u];
	head[u] = tot;
}

void init() {
	queue <int> q;
	
	memset(depth, 127, sizeof(depth));
	
	depth[0] = 0;
	depth[1] = 1;
	
	q.push(1);
	
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		
		for(int i = head[u]; ~i; i = edge[i].next) {
			int v = edge[i].to;
			
			if(depth[v] > depth[u] + 1) {
				depth[v] = depth[u] + 1;
				
				anc[v][0] = u;
				
				for(int k = 1; k <= 15; k ++ )
					anc[v][k] = anc[anc[v][k - 1]][k - 1];
				
				q.push(v);
			}
		}
	}
}

int lca(int u, int v) {
	if(depth[u] < depth[v])
		swap(u, v);
	
	for(int k = 15; k >= 0; k -- )
		if(depth[anc[u][k]] >= depth[v])
			u = anc[u][k];
	
	if(u == v)
		return u;
	
	for(int k = 15; k >= 0; k -- )
		if(depth[anc[u][k]] != depth[anc[v][k]]) {
			u = anc[u][k];
			v = anc[v][k];
		}
	
	return anc[u][0];
}

void inp() {
	scanf("%d", &n);
	
	memset(head, -1, sizeof(head));
	
	for(u = 2; u <= n; u ++ ) {
		scanf("%d", &v);
		
		v ++ ;
		
		add(u, v);
		add(v, u);
	}
}

void work() {
	init();
	
	scanf("%d", &q);
	
	while(q -- ) {
		scanf("%d", &m);
		
		int pos;
		
		scanf("%d", &pos);
		
		pos ++ ;
		
		for(int i = 1; i < m; i ++ ) {
			scanf("%d", &u);
			
			u ++ ;
			
			pos = lca(pos, u);
		}
		
		printf("%d\n", pos - 1);
	}
}

int main() {
	inp();
	work();
	
	return 0;
}
2024/6/12 12:01
加载中...