[bzoj4027][HEOI2015][兔子与樱花] (树形dp思想+玄学贪心)
2024-08-25 08:02:55
Description
很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成,编号从0到n-1,这n个分叉点由n-1个树枝连接,我们可以把它看成一个有根树结构,其中0号节点是根节点。这个树的每个节点上都会有一些樱花,其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m,对于每一个节点i,它的儿子节点的个数和i节点上樱花个数之和不能超过m,即son(i) + c_i <= m,其中son(i)表示i的儿子的个数,如果i为叶子节点,则son(i) = 0
现在兔子们觉得樱花树上节点太多,希望去掉一些节点。当一个节点被去掉之后,这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除,那么就会继续向上连接,直到第一个没有被删除的节点为止。
现在兔子们希望计算在不违背最大载重的情况下,最多能删除多少节点。
注意根节点不能被删除,被删除的节点不被计入载重。
Input
第一行输入两个正整数,n和m分别表示节点个数和最大载重
第二行n个整数c_i,表示第i个节点上的樱花个数
接下来n行,每行第一个数k_i表示这个节点的儿子个数,接下来k_i个整数表示这个节点儿子的编号
Output
一行一个整数,表示最多能删除多少节点。
Sample Input
Sample Output
HINT
对于100%的数据,1 <= n <= 2000000, 1 <= m <= 100000, 0 <= c_i <= 1000
数据保证初始时,每个节点樱花数与儿子节点个数之和大于0且不超过m
Solution
贪心,每次选择(直接儿子数+子树樱花数)最小的儿子,直到不能再选为止
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
int n,m,ans;
struct dt{
int x;
vector<int>e;
}a[N];
bool _cmp(int p,int q){
return a[p].x<a[q].x;
}
void dyn_pro(int x){
if(a[x].e.empty())
return;
for(int i=;i<a[x].e.size();i++)
dyn_pro(a[x].e[i]);
sort(a[x].e.begin(),a[x].e.end(),_cmp);
for(int i=;i<a[x].e.size();i++){
int tmp=a[a[x].e[i]].x-;
if(a[x].x+tmp<=m)
a[x].x+=tmp,
ans++;
else break;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
scanf("%d",&a[i].x);
for(int i=;i<n;i++){
int num,son;
scanf("%d",&num);
a[i].x+=num;
for(int j=;j<num;j++)
scanf("%d",&son),
a[i].e.push_back(son);
}
dyn_pro();
printf("%d\n",ans);
}
最新文章
- [Python] Pitfalls: Be Careful with os.chdir
- Android系统启动分析(Init->;Zygote->;SystemServer->;Home activity)
- oracle中的连接查询与合并查询总结
- 【linux】学习3
- JavaScript学习总结 Ajax和Http状态字
- POJ 2039
- mysql在update时,从其他select结果集更新表
- 五个新知识:微软SHA2补丁,亚信专业工具,微软官方文档,使用过期签名(附官方推荐链接),注意使用具有UAC的CMD
- 如何使用for循环连续的实例化多个对象!
- php 上传文件 $_FILES[&#39;&#39;][&#39;type&#39;]的值
- web项目编译出错时,原因之一,可能是build path 中order and Export引起
- python中关于字符串的操作
- github--hello,world(参考官网)
- php使用http_build_query,parse_url,parse_str创建与解析url详解
- Java框架spring 学习笔记(六):属性注入
- c#查找窗口的两种办法
- jquerymobile动态添的无索刷新
- windows 2008远程桌面企业协议号
- sprintboot 发布
- 使用dbms_output.put_line打印异常所在的行