比赛 20120718 评测结果 WWWWWWWWWW
题目名称 座位问题 最终得分 0
用户昵称 苏轼 运行时间 1.043 s
代码语言 C++ 内存使用 1.65 MiB
提交时间 2012-07-18 11:58:24
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<memory.h>
using namespace std;
int number;
bool used[100001]={0};
vector<int>a[100002];
int ans=0;
int b,answ=0;
void dfs(int q,int w);
bool use[100000]={0};
int main()
{
	freopen ("seat.in","r",stdin);
	freopen ("seat.out","w",stdout);
	cin>>number;
	for (int i=1;i<number;i++)
	{
		int xx,yy;
		cin>>xx>>yy;
		a[xx].push_back(yy);
		a[yy].push_back(xx);
	}
	for (int i=0;i<number;i++)
	{
		memset(use,0,number);
		answ=0;
		ans=0;
		cin>>b;
		dfs(ans,1);
	}
	return 0;
}
void dfs(int q,int w)
{
	if (answ)
		return;
	if (w==b)
	{
		cout<<ans<<endl;
		answ=1;
		used[w]=1;
		return;
	}
	else
	{
		for (int i=0;i<a[w].size()&&!use[a[w][i]];i++)
		{
			if (used[w])
				ans++;
			int c;
			c=a[w][i];
			use[c]=1;
			dfs(ans,c);
			use[c]=0;
			if (used[w])
				ans--;
		}
	}
}