挺简单的一个dp

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define maxn 10100
using namespace std;
const int INF = 0x3f3f3f3f;
vector<int>G[maxn];
void insert(int be, int en) {
G[be].push_back(en);
}
int n, m;
int h[maxn];
int b[maxn];
int vis[maxn]; int dfs(int x, int fa) {
h[x] = 1;
b[x] = 1;
if (vis[x] == 0) {
b[x] = INF;
}
if (vis[x] == 1) {
h[x] = INF;
}
for (int i = 0; i < G[x].size(); i++) {
int p = G[x][i];
if (p == fa) continue;
dfs(p, x);
h[x] += min(b[p], h[p] - 1);
b[x] += min(h[p], b[p] - 1);
}
return 0;
} int main() {
memset(vis, -1, sizeof(vis));
scanf("%d %d", &n, &m); int op;
for (int i = 1; i <= m; i++) {
scanf("%d", &op);
vis[i] = op;
}
int be, en;
int root = n;
for (int i = 1; i < n; i++) {
scanf("%d %d", &be, &en);
insert(be, en);
insert(en, be);
}
dfs(n, -1);
printf("%d\n", min(h[n], b[n]));
return 0;
}

  

最新文章

  1. NC台网震相走时获取及 HYPOINVERSE 格式读取
  2. Android 常用的adb命令
  3. javascript中求浏览器窗口可视区域兼容性写法
  4. MySQL 索引背后的数据结构及算法原理
  5. [收藏]ASP.NET MVC管道详述
  6. Java基础之线程——管理线程同步方法(BankOperation2)
  7. C# 控制台程序如何防止启动多个实例
  8. Linux资源控制-CPU和内存【转】
  9. EPEL库安装
  10. VS2010+Oracle11+Entity Framework4.1环境搭建及常见问题(转)
  11. C/C++笔试题整理
  12. Python--简单接口测试实例(一)
  13. Python菜鸟快乐游戏编程_pygame(4)
  14. RandomShuffleQueue
  15. theos安装详解
  16. jdbc之工具类DBUtil的使用
  17. 状态图绘制软件的使用---Gvedit
  18. 安卓手机安装虚拟定位的方法Xposed安装器+模拟位置(Xposed模块)
  19. sql developer Oracle 数据库 用户对象下表及表结构的导入导出
  20. nginx2

热门文章

  1. 利用IDEA构建springboot应用-配置文件
  2. 2019-8-31-dotnet-使用-lz4net-压缩-Stream-或文件
  3. 2019-1-29-Moq基础-判断方法被执行
  4. python基础之逻辑题(1)
  5. Samba服务器 安装
  6. 【codeforces 777E】Hanoi Factory
  7. 什么是响应式设计?响应式设计的基本原理是什么?如何兼容低版本的 IE?
  8. BraveOS正式版发布,希望大家下载使用
  9. while循环计算1-100和,1-100内偶数/奇数/被整除的数的和
  10. element-ui—dialog使用过程中的坑