比赛 至少完成十道练习 评测结果 AAAAAA
题目名称 无根树转有根树 最终得分 100
用户昵称 kZime 运行时间 0.492 s
代码语言 C++ 内存使用 8.90 MiB
提交时间 2017-05-22 08:50:15
显示代码纯文本
# include <bits/stdc++.h>
# define MAXN 1000023
using namespace std;
inline int gn() {
	int k = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}
struct edge {
	int to;
	edge *ne;
	inline edge() {
		to = 0;
		ne = NULL;
	}
	inline edge(int to_, edge *ne_) {
		to = to_, ne = ne_;
	}
}*head[MAXN];
inline void addedge(int fr, int to) {
	edge *e = new edge(to, head[fr]);
	head[fr] = e;
}
int fa[MAXN], n, u, m;
bool vis[MAXN];
int main() {
	freopen("wgs.in", "r", stdin);
	freopen("wgs.out", "w", stdout);
	n = gn();
	u = gn();
	for(int i = 1; i < n; i++) {
		int s = gn();
		int t = gn();
		addedge(s, t);
		addedge(t, s);
	}
	memset(fa, -1, sizeof(fa));
	queue <int> q;
	q.push(u);
	vis[u] = 1;
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		for(edge *e = head[x]; e; e = e->ne) {
			int y = e->to;
			if(~fa[y] || vis[y]) continue;
			fa[y] = x;
			q.push(y);
		}
	}
	m = gn();
	for(int i = 1; i <= m; i++) {
		printf("%d ", fa[gn()]);
	}
}