这道题涉及了组合分析和概率。本质上,当以一定的概率从给定的树中删除边时,您需要找到结果林的邻接矩阵的期望秩。
要解决这个问题,可以使用动态规划。我们用 \(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\)。
标签:frac,删除,题解,Random,这道题,Forest,CF1067E,顶点 From: https://www.cnblogs.com/BadBadBad/p/18149575/CF1067E