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

P7687 [CEOI 2005] Critical Network Lines TJ

P7687 [CEOI 2005] Critical Network Lines TJ


题意:

有一个 \(n\) 个点 \(m\) 条边的连通无向图。

一些点会给他连通的节点提供 \(A\) 类型服务,还有一些点会给他连通的节点提供 \(B\) 型服务。

问有几条边,满足删去这条边之后有一些点不能访问某种服务

\(n \le 10^5\), \(m \le 10^6\) 保证无重边。


因为只能删去一条边,所以点双里的所有点不受影响。

考虑缩点,缩完点就成了一棵树。

思考下什么时候一条边会对答案产生贡献,显然,就是垄断的情况下。

具体地,若一个子树内没有提供 \(A\) 服务,或者没有提供 \(B\) 服务,说明断掉这条边会对答案造成贡献。

只有这种情况了吗?

还可以全在子树内!即一个子树包含着所有提供 \(A\) 服务或者所有提供 \(B\) 服务的点也会造成影响。

只需要维护子树内提供 \(A, B\) 服务点的个数即可。


代码

http://www.jsqmd.com/news/425069/

相关文章:

  • 贪心做题笔记
  • 32并发输出速度519.87t/s!四卡T10(Turing, sm75) Qwen3-27B-FP8 并发吞吐量测试
  • 小学剑桥原版线上英语课推荐|家长实测不踩坑,选课直接抄作业 - 品牌测评鉴赏家
  • 现在分词
  • 从技术到口碑,惠耳神逸助听器彰显国产硬核实力 - 资讯焦点
  • 初中英语提分难?6个宝藏学习平台实测推荐,覆盖同步、口语、冲刺全场景 - 品牌测评鉴赏家
  • 2026年特氟龙输送带TOP10厂商评测排名 - 资讯焦点
  • 口碑较好的小型冰箱排行榜——2026年非常值得入手的选项 - 资讯焦点
  • 2026实测|初中英语线上辅导机构哪家好?避坑不花冤枉钱,家长直接抄作业 - 品牌测评鉴赏家
  • 2026线上少儿英语培训班推荐|家长闭眼抄作业不踩坑 - 品牌测评鉴赏家
  • 揭秘 Qt 的底层黑魔法:元对象系统 (MOS) 与元对象编译器 (MOC) 深度解析
  • 2026年知名的振动温度传感器厂家行业热门推荐 - 品牌鉴赏师
  • 小学生剑桥英语选课指南,3大主流品牌实测,新手家长直接抄作业 - 品牌测评鉴赏家
  • 西门子PLC结构化编程_数值改变检测标准块
  • 初中生必看|3款剑桥原版线上英语课实测,告别无效刷题 - 品牌测评鉴赏家
  • 2026男士防脱产品哪个牌子最好?十大明星级防脱生发品牌排行榜推荐,榜首效果惊艳 - 资讯焦点
  • 小学0基础线上英语课推荐|家长实测不踩坑!新手娃入门抄作业 - 品牌测评鉴赏家
  • NMN哪个牌子好?2026年全球NMN品牌深度横测:认准三项硬核指标 - 资讯焦点
  • 小学生线上剑桥英语选课|实测3家热门款,闭眼抄作业不踩坑 - 品牌测评鉴赏家
  • LangGraph4j 学习系列(7)-流式响应
  • hi3519dv500 Tsensor驱动
  • 基于深度学习的YOLO目标检测+智能计数系统之木材数量计数图像数据集 树木卡车图像计数数据集 detr图像数据集第10115期
  • TinyTeams.xyz:小团队创造大奇迹的科技名人堂
  • 基于机器学习的无人机的人群密度分析图像数据集 人员密度图像识别 无人机巡逻巡检人群数据集 cnn人员密度检测
  • 对于 UTF-16 的高低代理项码点的解析
  • 具身智能2026年产业图谱:智平方引领下的技术分化与价值落地
  • 春晚带火具身智能!2026 核心技术推荐 五强企业解锁智能新未来
  • PMMA塑料光纤怎么提高耐热性
  • 【系统分析师】10.4 问题分析
  • DSA期末考情分析