尧图网站建设 尧图网络
  • 首页
  • 关于我们
  • 服务项目
  • 案例展示
  • 建站流程
  • 资讯中心
  • 联系我们
首页/资讯中心/详情

CF1984E

CF1984E
📅 发布时间:2026/6/20 0:07:45

题目大意:

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

解题思路:

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

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

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

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

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

相关新闻

  • Go Modules 包管理 (Go 模块) - 详解
  • 2025 年导电炭黑厂家最新推荐榜:聚焦企业专利技术、品质管控及知名客户合作案例的权威解析
  • QOJ #967. Rectangle Painting 题解

最新新闻

  • Catberry状态管理终极指南:深入理解Store和Flux架构
  • 新疆正规旅行社推荐(附联系方式与官网) - 企业推荐官【官方】
  • Steamauto终极指南:如何实现游戏道具交易全自动化,24小时无人值守
  • 从理论到实践:TSLS两阶段最小二乘法在经济学实证研究中的完整流程解析
  • Python自动化获取QQ空间数据的终极方案
  • 2026杭州防水补漏维修团队实测盘点TOP4:杭州业主房屋渗漏修缮靠谱选择 - 宅安选房屋修缮

日新闻

  • 信任的进化:技术实现详解——如何用JavaScript构建博弈论模拟器
  • Terrakube自定义工作流:如何集成OPA、Infracost等工具扩展IaC能力
  • grunt-concurrent快速入门:5分钟学会并行运行Grunt任务

周新闻

  • 3步解锁iOS设备:applera1n激活锁绕过完全指南
  • 39 2026 人工智能证书终极盘点,普通人选 AI 证书可以从这些方向入手
  • Redis 暴露公网有多危险?从端口检查到补救步骤

月新闻

  • 【总结】入门篇:50句话让你记住架构核心概念
  • WeChatMsg技术方案解析:实现Mac微信数据自主管理的完整解决方案
  • WeChatMsg:革新性微信数据备份方案,打造你的专属数字记忆库

关于尧图

  • 公司简介
  • 团队介绍
  • 企业文化
  • 荣誉资质

服务项目

  • 定制开发
  • 电商建站
  • UI 设计
  • 运维服务

快速链接

  • 案例展示
  • 建站流程
  • 常见问题
  • 资讯中心

联系方式

  • 📍北京市朝阳区互联网产业园 A 座 10 层
  • 📞400-888-8888
  • ✉️contact@rkmt.cn
  • 🕐周一至周日 9:00-21:00

© 2024 北京尧图网络科技有限公司 版权所有 | 京 ICP 备 XXXXXXXX 号