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

广义串并联图とP6790 [SNOI2020] 生成树

广义串并联图とP6790 [SNOI2020] 生成树

前置知识:广义串并联图

定义广义串并联图为不存在与 \(K_4\)(即 \(4\) 个点的完全图)同胚的子图的连通无向图(同胚是指可以通过边的放缩而互相转化的图,即 \((x\leftrightarrow y\leftrightarrow z)\Leftrightarrow (x\leftrightarrow z)\) )。也即不存在四个点使得这个点之间有 \(6\) 条边不交的路径。

广义串并联图有性质:可以通过删除一度点、缩二度点、去除重边使原图变为一个点。这样我们在缩图过程中,每条边相当于原图的一个子图,我们可以在边上维护子图的信息,然后合并。

本题

\(G\) 是一个广义串并联图。证明:因为仙人掌对于任意四个点只有最多四条不交路径,多一条边后也最多五条,无法达到 \(K_4\) 的六条,故得证。

考虑对于每条边 \((u,v)\) 代表的子图,维护 \(f(u,v)\) 表示子图使得 \((u,v)\) 联通的方案数,即生成树数量。维护 \(g(u,v)\) 表示子图使得 \((u,v)\) 不连通的方案数,即子图分成两个生成树,\(u,v\) 各属于其中一个。接下来是合并信息。

  • 删除一度点时,对于一度点 \(u\) 和唯一连边 \((u,v)\)\((u,v)\) 一定要连通,所以直接计入答案 \(ans\gets ans\times f(u,v)\)
  • 缩二度点时,对于二度点 \(u\),和连边 \((u,x),(u,y)\)。要使 \((x,y)\) 联通,则 \((u,x),(u,y)\) 都要连通,即 \(f(x,y)=f(u,x)\times f(u,y)\)。要使 \((x,y)\) 不连通,则有一个不连通,且 \(u\) 要连通,所以 \(g(x,y)=f(u,x)\times g(u,y)+g(u,x)\times f(u,y)\)
  • 去除重边时,对于两条边 \((u,v)',(u,v)''\),若 \(u,v\) 连通,则两条边有且只有一个连通,即 \(f(u,v)=f(u,v)'\times g(u,v)''+g(u,v)'\times f(u,v)''\)。若 \(u,v\) 不连通,则两条边都不连通,\(g(u,v)=g(u,v)'\times g(u,v)''\)

实现时可以用 map 存一个点的连边,写一个 check(x) 函数,检查一个点是否是一度点或二度点,再递归 check。对于重边的判断,我们再加边时就要把重边合并掉,保证图中时时刻刻没有重边。

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

相关文章:

  • JUC: Java对象内存布局和对象头
  • Manim实现波浪形文字特效
  • JUC: synchronized与锁升级
  • lang / philipino / feilvbin / taglog / tajialu
  • Windows上安装2个不同版本的MySQL5.7和8.4
  • cron表达式,每月1号凌晨3点执行和每周4凌晨3点半执行
  • 2025.9.30
  • C#/.NET/.NET Core技术前沿周刊 | 第 56 期(2025年9.22-9.28)
  • 反转链表
  • 天津港口海鲜之旅全攻略(2025最新版)
  • tomcat创建bat启动,结合任务计划实现自动重启tomcat服务 - 详解
  • 实用指南:【论文精读】Few-Shot Object Detection with Attention-RPN and Multi-Relation Detector
  • Chromium V8类型混淆漏洞CVE-2025-10585安全分析
  • Claude 4.5 刚刚发布,能连肝 30 多个小时,史上最卷 AI 诞生
  • 香橙派5pro驱动开发(一)
  • Python 脚本遇到 SSL 证书问题
  • sa-token开发时遇到的问题
  • HR如何摆脱入离职事务性内耗?组织管理系统助力聚焦人才价值挖掘
  • 基于SpringAI构建大模型应用
  • C# TCP - 串口转发 - 实践
  • 【研发规范】Git 提交(commit)、CodeReview规范
  • PCIE 各个管脚的作用是什么?
  • Windows 11 局域网打印机共享设置
  • DailyPaper-2025-9-29
  • gpd winmax2 fedora42 睡眠秒唤醒问题
  • 国企人力资源管理系统怎么选?内行人推荐这8款,功能、服务双保障
  • spring service注入命名规则
  • 完整教程:基于岗课赛证的中职物联网专业“综合布线课程”教学解决方案
  • tensorflow加载和预处理信息
  • linux查询磁盘空间,查询指定目录的空间 df命令