记录编号	407544	评测结果	AAAAAA
题目名称	1642.无根树转有根树	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.270 s
提交时间	2017-05-22 10:53:54	内存使用	9.94 MiB

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

#ifndef LOCAL
const int MAXN = 1e6 + 10;
#else
const int MAXN = 1e3 + 10;
#endif

char buf[1<<21],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<21,stdin)),fs==ft)?EOF:*fs++;}
inline int in(void){ 
	char tmp = getc();
	int res = 0;
	while(!isdigit(tmp)) tmp = getc();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getc();
	return res;
}

struct EDGE{ 
	int to;
	EDGE *ne;

	EDGE(){;}
	EDGE(int _to, EDGE *_ne){ 
		to = _to, ne = _ne;
	}
};

inline void add_edge(int fr, int to);
inline void bfs(int sta);

int n, u;
EDGE *head[MAXN];
int father[MAXN];

int main(){ 
#ifndef LOCAL
	freopen("wgs.in", "r", stdin);
	freopen("wgs.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	n = in(), u = in();

	fill(father, father + n, -2);
	father[u] = -1;

	for(int i = 1, a, b; i < n; ++i){ 
		a = in(), b = in();
		add_edge(a, b);
	}

	bfs(u);

	n = in();

	for(int i = 1; i <= n; ++i){ 
		printf("%d ", father[in()]);
	}

	putchar('\n');
	return 0;
}

inline void add_edge(int fr, int to){ 
	static EDGE *p;
	p = new EDGE(to, head[fr]), head[fr] = p;
	p = new EDGE(fr, head[to]), head[to] = p;
	return ;
}

inline void bfs(int sta){ 
	static queue<int> que;
	static int u, v;
	
	que.push(sta);

	while(!que.empty()){ 
		u = que.front();
		que.pop();

		for(EDGE *p = head[u]; p; p = p->ne){ 
			if(father[(v = p->to)] ^ -2) continue;

			father[v] = u;
			que.push(v);
		}
	}

	return ;
}