codeforces 580C Kefa and Park(DFS)
2024-10-13 07:59:08
题目链接: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;
}
最新文章
- WCF 服务编程 - 常用绑定
- Excel通过身份证获取出生年月,性别,年龄,生肖,星座,省份等信息总结归纳
- HTML - 毛玻璃 滤镜 模糊
- Autoprefixer处理CSS3属性前缀
- mac os下得pycharm怎么设置mercurial?
- PHP(一)
- c/c++性能优化--- cache优化的一点杂谈
- 在unity中用鼠标实现在场景中拖动物体,用鼠标滚轮实现缩放
- swool安装
- 1010: [HNOI2008]玩具装箱toy [dp][斜率优化]
- Windows同时安装Python2、Python3兼容运行
- BOM(浏览器对象模型)
- vuex-getter
- 报错解决——Failed to load resource: the server responded with a status of 404 (Not Found) favicon.ico文件找不到
- linux学习笔记-13.进程控制
- hdu1087 dp(最大上升子序列和)
- Kafka安装kafka-manager
- ip辅助和别名的区别
- C++ Primer Plus学习:第九章
- Ubuntu16.4 修改静态ip地址
热门文章
- C++继承与派生(原理归纳)
- Centos 6.2 安装mysql5.5
- Apache Thrift - 可伸缩的跨语言服务开发框架
- [Js]焦点图轮播效果
- bzoj 2152: 聪聪可可
- PHP安装pthreads多线程扩展教程[windows篇]
- HDU 4890 One to Four(2014 Multi-University Training Contest 3)
- zoj2132-The Most Frequent Number
- TDBGridEh的 搜索面板 TDBGridSearchPanel
- 基于Lumisoft.NET组件的POP3邮件接收和删除操作