记录编号	453376	评测结果	AAAAAWWWWWWWWWWWWWWW
题目名称	[NOIP 2016]天天爱跑步	最终得分	25
用户昵称	Regnig Etalsnart	是否通过	未通过
代码语言	C++	运行时间	1.085 s
提交时间	2017-09-21 14:41:10	内存使用	6.88 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=300000;
int n,m,W[maxn],s[maxn],t[maxn],ans[maxn],i,j;
int dep[1000];
vector<int>G[maxn];
void print()
{
	for(i=1;i<=n;i++)printf("%d ",ans[i]);
	printf("\n");
	return;
}
void bfs(int begin,int end)
{
	memset(dep,-1,sizeof(dep));
	queue<int>Q;
	while(!Q.empty())Q.pop();
	Q.push(begin);
	dep[begin]=0;
	while(!Q.empty())
	{
		int now=Q.front();Q.pop();
		for(int ii=0;ii<G[now].size();ii++)
		{
			int to=G[now][ii];
			if(dep[to]==-1)
			{
				dep[to]=dep[now]+1;
				Q.push(to);
				if(to==end)return;
			}
		}
	}
}
void dfs(int now)
{
	if(W[now]==dep[now])ans[now]++;
	for(int ii=0;ii<G[now].size();ii++)
		if(dep[now]-dep[G[now][ii]]==1)dfs(G[now][ii]);
	return;
}
void solve1()//AAWWWWWWWWWWWWWWWWWW
{
	for(i=1;i<=m;i++)if(!W[s[i]])ans[s[i]]++;
	print();
	return;
}
void solve2()//AAAAWWWWWWWWWWWWWWWW
{
	for(i=1;i<=m;i++)ans[s[i]]++;
	print();
	return;
}
void solve3()
{
	for(i=1;i<=m;i++)
	{
		bfs(s[i],t[i]);
		dfs(t[i]);
	}
	print();
	return;
}
int Main()
{
	freopen("runninga.in","r",stdin);freopen("runninga.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(i=1;i<=n;i++)scanf("%d",&W[i]);
	for(i=1;i<=m;i++)scanf("%d%d",&s[i],&t[i]);
	if(n==991)solve1();
	else if(n==992)solve2();
	else if(n<=993)solve3();/*
	else if(n==99994)solve4();
	else if(n==99995)solve5();
	else if(n==99996)solve6();
	else if(n==99997)solve7();
	else if(n==299998)solve8();*/
	return 0;
}
int main(){;}
int syy=Main();