AGC058F

· · 题解

看了好久，所以我来写一下。

这个式子直接做肯定是没法做的，我们考虑转换成组合意义，\dfrac{1}{n} 的存在提示我们转换成概率。由于每次是选一条边，边的个数是 n - 1，概率理应是 \dfrac{1}{n-1} 的，必须加点东西。加边补全的方式不可行，它可能会重复计算自己，想一想很复杂。

此时有一个人类智慧想法：我们把所有边新建一个点，称为边点 e，每个边再带一个大小为 -1 的辅助点，在模意义下就是加一个大小为 P - 1 的点。那么总点数就是 n 了。

此时我们定义这个新树为 T^{\prime}，那么答案就是：T^{\prime} 的点排列满足对于所有边点，其出现位置都比其相邻点小的概率。证明就是，对于一个子树，你把求上述概率的式子（每次删除一个边点，分成若干子树求概率）列出来，可以发现跟原题式子是完全一样的。

我们把这个点的大小关系从大到小连边，可以连出这样的图：

（黑色点是边点，蓝色点是大小为 -1 的点）

这个东西的边方向不统一，考虑容斥。将所有向上的边改成向下或没有边，容斥系数就是改成向下的边的数量。

树形背包，设 f_{u,i} 为考虑 u 子树以 u 为根，其外向树大小为 i 满足条件的概率。

两种情况，第一种是将边改下。

你要乘上指向的边点作为根的概率 \dfrac{1}{j} 和容斥系数 -1。j 是你枚举的 v 外向树大小，用树形背包转移。

然后是删掉的情况。

同样乘上 \dfrac{1}{j}。

最后还要乘上 u 概率 \dfrac{1}{i}。

最后答案相当于 \sum_{i = 1}^{n}{f_{1,i}}。

upd：之前说过一个，若我们去掉 \frac{1}{n} 会是什么，它是错的，但是我觉得他是问题转化之后，非边点之间无区别的方案数，不知道对不对。求高手指点。