当前位置: 首页 > news >正文

CF1984E

题目大意:

你现在有一棵树,每次你可以选择一个点,将这个点变成根,然后递归处理他的大小不为 1 的儿子们。
请问度数为 1 的点的数量最多有多少。
\(n \le 2 \times 10^5\)

解题思路:

考虑简化他的题意,考虑什么时候停止,就是当他任意一条边上的两个点至少有一个被选择当根的时候、

那么对于所有没被选中的点,他在最终的状态下一定是叶子。
而对于选中的点,因为他一定有儿子,所以当根只有一个儿子时答案会多一。

而只有一个儿子当且仅当他是叶子。

也就是你要选出一个独立集,如果他不包含所有的叶子,那么答案会多一。
也就是设个 \(f_{u,0/1,0/1}\) 表示 \(u\) 子树内,它本身选没选,有没有全选叶子的最大大小。

这题的难点是转化题意,自己做的时候凭感觉猜了个与独立集相近的东西,以后想不到啥对的东西可以多往这些概念上想。

http://www.rkmt.cn/news/30336.html

相关文章:

  • Go Modules 包管理 (Go 模块) - 详解
  • 2025 年导电炭黑厂家最新推荐榜:聚焦企业专利技术、品质管控及知名客户合作案例的权威解析
  • QOJ #967. Rectangle Painting 题解
  • L07_2
  • 2025 年最新地磅制造厂家推荐排行榜:聚焦品质创新服务,助力企业精准选优质地磅汽车衡 / 大型 / 可移动 / 100 吨 / SCS 型 / 自动称重地磅推荐
  • layui多文件上传表格
  • layui静态表格防止被内容撑开变形
  • 2025 年最新推荐工作服实力厂家排行榜权威发布,助力企业精准挑选优质定制厂商商务 / 车间 / 企业 / 透气工作服厂家推荐
  • 2025年废水处理厂家权威推荐榜单:工业废水、生活污水处理设备及解决方案供应商深度解析
  • 基于Springboot的教学课程管理系统 - 指南
  • 深入解析:【从图片到3D几何体/动画】3DMAX像素几何体插件PixelGeometry使用方法
  • 你的excel二级三级多级下拉菜单为啥不好用?讲清楚INDIRECT函数用法!
  • 权威调研榜单:苏州吊车租赁公司TOP3榜单好评深度解析
  • 从零开始制作 MyOS(二)
  • 2025 年钛白粉源头厂家最新推荐排行榜:高分子材料领域专家解析改性技术与行业应用案例
  • 如何通过限制网络访问来降低服务器被攻击的风险? - 指南
  • 2025年废气治理设备厂家推荐排行榜,废气处理设备,工业废气净化装置,有机废气处理系统公司精选
  • 2025年提升机厂家权威推荐榜:自动提升机、垂直提升机、斗式提升机,高效输送设备源头厂家精选
  • 2025年企业数字化展厅定制厂家权威推荐榜单:企业数字展厅/企业创意展厅/企业智能展厅源头厂家精选
  • 2025年清洗剂厂家权威推荐榜:水基型清洗剂、工业清洗剂、精密仪器清洗剂源头厂家综合测评与选购指南
  • 18 龟兔赛跑代码和callable的基础结构
  • Day4表格中合并单元格
  • 2025年环保设备厂家推荐排行榜,废气处理设备,废水处理设备,噪音治理设备公司推荐,专业实力与环保方案深度解析
  • Unreal:如何在UE中实现SSH隧道,安全访问远程服务
  • 2025 年最新推荐煎饼机优质厂家榜单:涵盖全自动 / 半自动 / 仿手工 / 导热油等多类型,附中国食品机械协会测评权威结果
  • 102302156 李子贤 数据采集第一次作业
  • docker 进入容器:
  • 密码和验证码防止暴力破解 - 详解
  • Paper: SALT: Step-level Advantage Assignment for Long-horizon Agents via Trajectory Graph
  • 别慌!恢复已删除数据的 10 个卓越技巧,小白也能会