比赛 至少完成十道练习 评测结果 AAAAAA
题目名称 无根树转有根树 最终得分 100
用户昵称 Ostmbh 运行时间 0.684 s
代码语言 C++ 内存使用 15.57 MiB
提交时间 2017-05-20 21:52:16
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=1000000+10;
vector<int>A[maxn];
int fa[maxn]={0};
queue<int>q;
int main(){
	freopen("wgs.in","r",stdin);
	freopen("wgs.out","w",stdout);
	memset(fa,-1,sizeof(fa));
	int n,d;
	scanf("%d %d",&n,&d);
	int x,y;
	for(int i=1;i<n;i++){
		scanf("%d %d",&x,&y);
		A[x].push_back(y);
		A[y].push_back(x);
	}
	q.push(d);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<A[x].size();i++){
			int u=A[x][i];
			if(u!=fa[x]){
				fa[u]=x;
				q.push(u);
			}
		}
	}
	int m;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&x);
		printf("%d\n",x==d?-1:fa[x]);
	}
return 0;
}