CF1067E Random Forest Rank 题解

· · 题解

这道题涉及了组合分析和概率。本质上，当以一定的概率从给定的树中删除边时，您需要找到结果林的邻接矩阵的期望秩。

要解决这个问题，可以使用动态规划。我们用 f(u,v) 表示当删除边 (u,v) 时，由以顶点 v 为根的子树中的顶点形成的林的期望秩。这里，u 和 v 是树中的相邻顶点。

f(u, v) = \frac{1}{2} (f(u, v) + 1) + \frac{1}{2} (f(v, u) + 1) + \frac{1}{4} (f(u, u) + f(v, v) - 1)

第一项说明了当边 (u,v) 未被删除时的情况，第二项说明了边 (u,v) 被删除的情况，第三项说明了与 v 相关的两个边都被删除的情形。

那么这道题的答案就出来了，就是是树中所有边 (u,v) 上的所有 f(u,v) 值的总和，乘以 2^{n-1}，取模 998244353。