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