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

using namespace std;

const int MC=1000001;
vector<int> map[MC];
int N,START,M;
int father[MC];

void bfs(int a)
{
	int i,temp;
	deque<int> Q;
	Q.push_back(a);
	while(!Q.empty())
	{
		temp=Q.at(0);
		Q.pop_front();
		for(i=0;i<map[temp].size();i++)
		{
			if(father[map[temp][i]]==0)
			{
				father[map[temp][i]]=temp;
				Q.push_back(map[temp][i]);
			}
		}
	}
}
int main()
{
	freopen("wgs.in","r",stdin);
	freopen("wgs.out","w",stdout);
	cin>>N>>START;
	int i,A,B;
	for(i=1;i<N;i++)
	{
		cin>>A>>B;
		map[A].push_back(B);
		map[B].push_back(A);
	}
	father[START]=-1;
	bfs(START);
	cin>>M;
	for(i=1;i<=M;i++)
	{
		cin>>A;
		if(i!=M)
			cout<<father[A]<<' ';
		else
			cout<<father[A]<<endl;
	}
	return 0;
}