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

CF1984E

题目大意:

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

解题思路:

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

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

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

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

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

http://www.hskmm.com/?act=detail&tid=38942

相关文章:

  • 2025年市面上美国留学品牌、口碑好的美国留学产品、2025年美国留学渠道商、评价高的美国留学服务商、美国留学品牌推荐榜综合评测
  • 2025年市面上美国留学品牌、2025年美国留学品牌、口碑好的美国留学品牌、热门的美国留学品牌、美国留学品牌推荐榜深度评测
  • gu
  • 2025 年导电炭黑厂家最新推荐榜:聚焦企业专利技术、品质管控及知名客户合作案例的权威解析
  • docker 端口映射
  • L07_2
  • C语言基础补全
  • 「学习笔记」PHP 基础
  • 2025 建筑陶粒厂家最新推荐榜:回填 / 粘土 / 滤料 / 混凝土等多品类优选,实力企业权威测评推荐!
  • 251025
  • 2025 年最新地磅制造厂家推荐排行榜:聚焦品质创新服务,助力企业精准选优质地磅汽车衡 / 大型 / 可移动 / 100 吨 / SCS 型 / 自动称重地磅推荐
  • 关于我:新的开始,新的记录
  • 关于 NoiLinux 系统和 CodeBlocks 的考场使用
  • 2025 年知识库应用平台最新推荐排行榜!企业 / 个人 / 协同 / 智能等多场景适配,附权威测评与选择指南
  • 深入解析:深度学习调参指南:Batch Size的选择策略与实践
  • 2025 年最新推荐工作服实力厂家排行榜权威发布,助力企业精准挑选优质定制厂商商务 / 车间 / 企业 / 透气工作服厂家推荐
  • 2025年废水处理厂家权威推荐榜单:工业废水、生活污水处理设备及解决方案供应商深度解析
  • 2025年仿石漆厂家推荐排行榜,外墙仿石漆,内墙仿石漆,防霉仿石漆,水包水/水包砂仿石漆,耐污自洁仿石漆公司精选
  • 你的excel二级三级多级下拉菜单为啥不好用?讲清楚INDIRECT函数用法!
  • 权威调研榜单:航空警示球厂家TOP3榜单好评深度解析
  • 死锁 (Deadlock) 深度解析 - 详解
  • 解压小猫
  • 2025年家具厂家推荐排行榜:实木家具、定制家具、办公家具、软体家具、智能家具源头厂家精选
  • 2025 厨房排烟安装公司最新推荐榜:实力品牌服务与工艺解析及选择指南饭店/商用/罩/系统/厨房排烟管道专业服务公司推荐
  • 权威调研榜单:苏州吊车租赁公司TOP3榜单好评深度解析
  • 从零开始制作 MyOS(二)
  • 2025年高压加速老化设备厂家推荐排行榜,高压加速老化HAST,高压加速老化PCT,热流仪源头厂家专业测评与选购指南
  • 2025年摄像头防爆外壳供货商权威推荐榜单:监控摄像头外壳/摄像头外壳/路口警示道灯外壳源头厂家精选
  • 2025 液态硅胶设备源头厂家最新推荐榜:行业协会权威测评发布,品质与服务双维度精选
  • 2025 年阳台光伏厂家最新推荐排行榜:权威测评解析逆变器、储能及光伏板优质企业阳台太阳能光伏/储能/发电/阳台光伏板优质厂家推荐