CF2191F 题解

考虑 $v$ 是 prufer 点的充要条件：$v$ 和 $n$ 直接相连；$v$ 是 $n-1$ 的祖先，因为不是 $n-1$ 祖先的点总先于 $n-1$ 被删除。然后分讨：

• $n-1$ 和 $n$ 连通：只有同时是 $n$ 的儿子和是 $n-1$ 的祖先的那个点的答案不是 $0$，此时所有 $n^{k-2}\prod\limits^k_{i=1}s_i$ 种方案都合法。
• 否则对每个点 $v$ 考虑。下面默认 $v$ 和 $n$ 已经有边（没有边的话直接连上再处理即可），这时限制只剩 $n-1$ 所在的树要接到 $v$ 的子树里。答案是总方案数乘 $v$ 子树的大小 $s_v$ 除 $n$ 所在的这棵树总共的大小 $S$，即 $\frac{s_v}{S}n^{k-2}\prod\limits^k_{i=1}s_i$。这是关键的一步，因为所有方案是对称的，任意抽取一个方案，把 $n-1$ 所在的子树接到 $v$ 那一侧的概率正好就是 $\frac{s_v}{S}$。如果 $(v,n)$ 是手动添加上去的，这个公式应该在加边后的新图中应用，也就是 $\frac{s_v}{s_v+S}n^{k-3}(s_v+S)\prod\limits_{i≠c_v,c_n}s_i$，其中 $c_x$ 代表 $x$ 所在的联通块。