codeforces 580C Kefa and Park(DFS)

题目链接:http://codeforces.com/contest/580/problem/C

#include<cstdio>
#include<vector>
#include<cstring>
#define MAX 100010
using namespace std;
vector <int> a[MAX];
int visit[MAX];
int cat[MAX];
int leaf[MAX];
int ans,m;
void dfs(int x,int numcat)
{
if(visit[x])
return;
else
visit[x]=1;
if(cat[x])
numcat++;
else
numcat=0;
if(numcat>m)
return;
if(leaf[x]==1&&x!=1)
ans++;
int len=a[x].size();
for(int i=0;i<len;i++)
dfs(a[x][i],numcat);
}
int main()
{
int n,i,j,k,numcat;
while(~scanf("%d%d",&n,&m))
{
numcat=ans=0;
memset(visit,0,sizeof(visit));
memset(leaf,0,sizeof(leaf));
for(i=1;i<=n;i++)
{
scanf("%d",&cat[i]);
a[i].clear();
}
for(i=1;i<=n-1;i++)
{
scanf("%d%d",&j,&k);
a[j].push_back(k);
a[k].push_back(j);
leaf[j]++;
leaf[k]++;
}
dfs(1,0);
printf("%d\n",ans);
}
return 0;
}
上一篇:Android图片缓存框架Glide


下一篇:TOPSIS法(理想解法)