题目意思:给你一棵树,然后每个叶子节点会有一家餐馆,你讨厌猫,就不会走有连续超过m个节点有猫的路,然后问你最多去几家饭店

思路:直接DFS

Example

Input
4 1
1 1 0 0
1 2
1 3
1 4
Output
2
Input
7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
Output
2
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn=1e5+;
int flag[maxn];
vector<int>e[maxn];
int n,m,ans=;
void dfs(int u,int num,int fa)
{
for(int i=;i<e[u].size();i++)
{
int v=e[u][i];
if(v==fa)
continue;
if(flag[v]==)
{
if(e[v].size()==)
ans++;
dfs(v,,u);
}
else if(num+<=m)
{
if(e[v].size()==)
ans++;
dfs(v,num+flag[v],u);
}
}
} int main()
{
cin>>n>>m;
for(int i=;i<=n;i++)
cin>>flag[i];
for(int i=;i<n;i++)
{
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(,flag[],-);
cout<<ans<<endl;
}

最新文章

  1. SQL Server 存储过程生成insert语句
  2. NGUI 滑动特效之中间放大滚动
  3. ubuntu16.04安装virtualbox5.1失败 gcc:error:unrecognized command line option ‘-fstack-protector-strong’
  4. Angular $scope和$rootScope事件机制之$emit、$broadcast和$on
  5. PyCharm不能自动import解决方法_PyCharm cannot auto import package troubleshooting
  6. 文本域的宽度和高度应该用cols和rows来控制,还是 用width和height来控制
  7. Linux14.04安装Mysql Linux公社
  8. android自定义控件(2)-拖拽实现开关切换
  9. angular常见坑洞
  10. 转!sqlServer2000 表连接查询
  11. 函数fil_node_create
  12. Nginx介绍 分类: Nginx 服务器搭建 2015-07-13 10:50 19人阅读 评论(0) 收藏
  13. 用UBOOT自带loadb命令加载应用程序到SDRAM中运行的方法
  14. Docker使用Link与newwork在容器之间建立连接
  15. leetcode978
  16. C++生成斐波拉其数列
  17. python tornado异步性能测试
  18. 无刷新上传图片以及使用C#语言
  19. Error running : Address localhost:1099 is already in use
  20. A B C D类网络地址

热门文章

  1. IOS中使用百度地图定位后获取城市坐标,城市名称,城市编号信息
  2. 【2018 ICPC亚洲区域赛沈阳站 L】Tree(思维+dfs)
  3. Mysql存储过程查询结果赋值到变量
  4. mysql 查询各个阶段所消耗的时间
  5. IDEA中使用插件添加更多可选择的主题,使代码高亮,缓解视觉疲劳
  6. 什么是token及怎样生成token
  7. 【转载】在C#中主线程和子线程如何实现互相传递数据
  8. STM32(4)——系统时钟和SysTick
  9. docker理论基础
  10. django中的ContentType使用