比赛 至少完成十道练习 评测结果 AAAAAA
题目名称 无根树转有根树 最终得分 100
用户昵称 Emine 运行时间 1.953 s
代码语言 C++ 内存使用 15.57 MiB
提交时间 2017-05-23 10:50:13
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<vector>
using namespace std;

vector<int> map[1000001];
int n,g,m;
int fa[1000001];

void bfs(int a){
	int i,tmp;
	deque<int> Q;
	Q.push_back(a);
	while(!Q.empty())
	{
		tmp=Q.at(0);
		Q.pop_front();
		for(i=0;i<map[tmp].size();i++){
			if(fa[map[tmp][i]]==0){
				fa[map[tmp][i]]=tmp;
				Q.push_back(map[tmp][i]);
			}
		}
	}
}

int main()
{
	freopen("wgs.in","r",stdin);
	freopen("wgs.out","w",stdout);
	cin>>n>>g;
	int a,b;
	for(int i=1;i<n;i++){
		cin>>a>>b;
		map[a].push_back(b);
		map[b].push_back(a);
	}
	fa[g]=-1;
	bfs(g);
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a;
		if(i!=m)
			cout<<fa[a]<<' ';
		else
			cout<<fa[a]<<endl;
	}
	return 0;
}