Codeforces Round #321 (Div. 2) C Kefa and Park(深搜)
2024-08-29 10:21:12
dfs一遍,维护当前连续遇到的喵的数量,然后剪枝,每个统计孩子数量判断是不是叶子结点。
#include<bits/stdc++.h>
using namespace std; const int maxn = 2e5+;
int a[maxn];
int head[maxn],nxt[maxn<<],to[maxn<<],ect; inline void addEdge(int u,int v)
{
to[ect] = v;
nxt[ect] = head[u];
head[u] = ect++;
} int ct[maxn],m,cnt;
void dfs(int u,int f)
{
if(a[u]) ct[u] = ct[f]+;
if(ct[u]>m) return;
int ch = ;
for(int i = head[u]; ~i ; i = nxt[i]){
int v = to[i];
if(v == f) continue;
ch++;
dfs(v,u);
}
if(!ch) { cnt++; }
} //#define LOCAL int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
memset(head,-,sizeof(head));
int n; scanf("%d%d",&n,&m);
for(int i = ; i <= n; i++) scanf("%d",a+i);
for(int i = ; i < n; i++){
int u,v; scanf("%d%d",&u,&v);
addEdge(u,v); addEdge(v,u);
}
dfs(,);
printf("%d",cnt);
return ;
}
最新文章
- EntityFramework.Extended 实现 update count+=1
- iOS cocoapods升级及问题
- iOS开发——高级技术精选OC篇&;Runtime之字典转模型实战
- Object C学习笔记23-继承,重写,重载
- System Services ->; Memory Management ->; About Memory Management
- 【转】修改xampp的mysql默认密码
- LeetCode FindMinimuminRotatedSorteArray &;&;FindMinimuminRotatedSorteArray2
- (亲测)设​置​m​y​e​c​l​i​p​s​e​打​开​默​认​工​作​空​间
- linux enable命令学习
- javascript事件设计模式
- 第1阶段——u-boot分析之make指令(2)
- String 类
- 简单聊一聊那些svg的沿路径运动
- codeforces 975C Valhalla Siege
- Nginx 设置负载均衡
- 37-Arrays.sort() 由大到小排序 和 对象数组排序
- Eigen教程(7)
- python-docx操作word文件(*.docx)
- SpringMVC 多个数据源 配置多个事物管理器 Multiple Transaction Managers
- 编写 Target 检测 MSBuild / dotnet build 此次编译是否是差量编译
热门文章
- 优酷电视剧爬虫代码实现一:下载解析视频网站页面(4)补充: Java正则表达式Matcher.group(int group)相关类解析
- Linux 之问题集锦(一)
- C# 写 LeetCode easy #13 Roman to Integer
- ";Mysql has gone away";的几种可能
- PJzhang:经典子域名爆破工具subdomainsbrute
- Codeforces Round #459 (Div. 2)The Monster[匹配问题]
- jenkins 找不到mvn 命令
- 洛谷P2513 [HAOI2009]逆序对数列
- java基础第九篇之final和内部类等
- 运用html常用标签和css定位等学做模仿百度导航页面