比赛 至少完成十道练习 评测结果 AAAAAA
题目名称 无根树转有根树 最终得分 100
用户昵称 Hyoi_ctime 运行时间 1.950 s
代码语言 C++ 内存使用 15.57 MiB
提交时间 2017-05-22 09:30:02
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
vector<int>ll[1000001];
int n,ks,m;
int fa[1000001];
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<ll[temp].size();i++)
		{
			if(fa[ll[temp][i]]==0)
			{
				fa[ll[temp][i]]=temp;
				q.push_back(ll[temp][i]);
			}
		}
	}
}
int main()
{
	freopen("wgs.in","r",stdin);
	freopen("wgs.out","w",stdout);
	cin>>n>>ks;
	int i,x,y;
	for(i=1;i<n;i++)
	{
		cin>>x>>y;
		ll[x].push_back(y);
		ll[y].push_back(x);
	}
	fa[ks]=-1;
	bfs(ks);
	cin>>m;
	for(i=1;i<=m;i++)
	{
		cin>>x;
		if(i!=m){
			cout<<fa[x]<<' ';
		}
		else
		{
			cout<<fa[x]<<endl;
		}
	}
	return 0;
}