不妨考虑把期望联通快个数拆成每条边是否出现的概率乘上这条边是否出现对联通块个数的增减数量。
想要得到这个增减数量，对于一个子树内我们只需要维护子树根、极左叶子节点、极右叶子节点的连通性即可。
实现上，我们可以用并查集等手段提前预处理出所有的转移和系数。
QOJ.ac
QOJ
Discussion #2718 for Problem #20244. Island
Type: Editorial
Status: Open
Posted by: Cocoly1990
Posted at: 2026-09-14 16:54:21
Last updated: 2026-09-14 16:58:21
New Editorial for Problem #20244
Comments
No comments yet.