zjoi2017 仙人掌
2024-09-01 06:05:45
题解:
好难的dp啊。。。看题解看了好久才看懂
http://blog.csdn.net/akak__ii/article/details/65935711
如果一开始的图就不是仙人掌,答案显然为0,可以Tarjan判断。
环显然不能产生贡献,所以可以把环边都断开。
现在模型转化为,给定一棵树,用路径去覆盖树上的每一条边,且路径不能相交,求方案数。
设fifi表示做完了ii的子树,且没有路径可以向上扩展。
设gigi表示做完了ii的子树,且有路径可以向上扩展。
设hihi表示有ii个点,它们之间匹配的方案数。
记numnum为点xx的儿子个数,那么显然 hi=hi−+hi−×(i−)
hi=hi−+hi−×(i−) fx=Πgson×hnum
fx=Πgson×hnum gx=fx+Πgson×hnum−×num
gx=fx+Πgson×hnum−×num 简单解释一下:
hihi转移的时候考虑当前第ii个儿子的选择,如果这个儿子不匹配,那就有hi−1hi−1种方案,如果匹配,那就可以和前面i−1i−1个儿子中的一个匹配,方案是(i−)×hi−(i−)×hi−
fxfx的转移:每个儿子都必须要可以往上扩,且各个儿子之间相对独立所以是ΠgsonΠgson,然后一共有hnumhnum种儿子的匹配方案,所以乘起来就是所有可能的方案。
gxgx的转移:首先xx自己可以往上扩展,方案就是fxfx,然后xx还可以选择一个儿子,记这个儿子为yy,匹配方案为gygy,那么剩下的儿子有Πson!=y gson×hnum−1Πson!=y gson×hnum−1种方案,乘起来就是Πgson×hnum−1Πgson×hnum−1由于yy的取值有numnum种选择所以还要乘上numnum。
最新文章
- grid style
- mongodb-索引
- XE7 Update 1 选 iOS 8.1 SDK 发布 iPhone 3GS 实机测试
- [读书笔记]C#学习笔记四: C#2.0泛型 可控类型 匿名方法和迭代器
- C++——类继承
- PLA 多维情况下的vc维
- 201521123017 《Java程序设计》第3周学习总结
- 【学习笔记】Hibernate 一对一关联映射 组件映射 二级缓存 集合缓存
- Web前端之iframe详解
- 学习Python第七天
- Spring 的属性注入
- cdnbest如何查看站点操作日志(同步日志)
- NFS Server宕机后,NFS Client主机上df命令挂死
- 初征——NOIP2018游记
- 亲历H5移动端游戏微信支付接入及那些坑(一)——支付方式与坑
- 常见的接口与类 -- Comparable
- 洛咕 P2155 [SDOI2008]沙拉公主的困惑
- SQL语言的增删改查
- spring boot加mybatis使用Map返回时,当值为空时属性也会没有(转)
- jvm垃圾回收策略