CF1067E 题解
2024-10-22 04:49:32
题意
给定一棵 \(n\) 个节点的树,每条边有 \(\frac{1}{2}\) 的概率出现,可以得到一个森林,求这个森林邻接矩阵的秩的期望。
\(1\le n\le5\times10^5\)。
题解
此题关键在于一个重要结论:一个森林邻接矩阵的秩等于其最大匹配数 \(\times2\)。下面对其进行证明。
我们先看邻接矩阵的秩等于 \(n\) 的充要条件。由行列式的定义,有
\[\sum\limits_{\pi}(-1)^{\tau(\pi)}\prod\limits_{i=1}^nA_{i,\pi_i}\neq0
\]
\]
若后面的积 \(\neq0\),则所有点都向另一点连边,且不重复。而森林无环,于是可以得出其存在完美匹配。而一个森林最多存在一个完美匹配,从叶子向上贪心即证。那么充要条件就是存在完美匹配。
再来看秩不等于 \(n\)。由某条奇妙的定理,我们知道对称矩阵的最大子式一定是主子式。那么其就是原图的一个导出子图。最大的存在完美匹配的导出子图,即是原图的最大匹配。于是证毕。
然后就可以算了。由期望的线性性,对每条边求其为匹配的概率,也就是方案数。但由于我们判断匹配的方式是从叶子向上的贪心,这不太好算。换个形式,对每个点求其与儿子匹配的方案数。这就是一个简单的树形 \(\text{DP}\) 了。于是此题得解。
最新文章
- 探讨webapp的SEO难题(上)
- 初学JAVA 感想
- GTD
- mybatis 使用记录
- 【网络编程】——connect函数遇见EINTR的处理
- c/c++指针总结[pointer summary]
- php对比辨析之 mysql_escape_string &; mysql_real_escape_string &; addsalshes
- 笨笨-歌词伴侣V1.2(酷狗KRC转LRC,LRC歌词批量下载)
- FireFly 服务端 Unity3D黑暗世界 客户端 问题
- HBuilder手机Iphone运行提示“未受信用的企业级开发者”
- 怎样在WIN7系统下安装IIS
- iOS 电商购物车倒计时时间计算
- MVC分页控件的使用
- angularjs+ionic+'h5+'实现二维码扫描功能
- hdu5788 level up
- 03、NetCore2.0下Web应用之搭建最小框架
- 网络协议与OSI体系结构
- [复习]动态dp
- ActiveSync中的http内容组织
- 存储过程传入datatable