nfls-3c

两人博弈，随机一棵 $n$ 个点的树，每条边边权在 $[0,m]$ 里随机。

现在随机一个点放一枚棋子，两人轮流移动，每次只能选边权 $>0$ 的边移动，然后边权 $-1$ 。

求先手必胜概率，答案对质数 $p$ 取模。

$n\le 10^6$​ 。

首先解决这个博弈问题，分讨归纳一下可以发现，边权是可以对 $2$ 取模的，也就是边权变成了只有 $0,1$ ，也就是每条边存在与否。

那么每个点就只有胜或者负，一个点负的条件就是所有儿子都是胜。

此时有两种做法：

先直接去容斥，钦定根是胜，那么减去负的，也就是儿子都是胜，也就是一个递归下去的过程。

那么一个容斥的状态就是到每个叶子处停止，容斥系数就是总点个数。

此时容斥出的就是一个

然后变成一个子问题：

$n$ 个有编号点形成 $k$ 个联通块的有根森林的方案数。

首先有一个很无脑的拉格朗日反演做法，直接 $\hat F=xe^{\hat F}$，然后反演求 $\hat F^k$ 即可。

然后也有一个不难的 prufer 做法。

答案就是钦定 $k$ 个根之后再去乘以 $\dbinom{n}{k}$。

那么钦定 $k$ 个根分别是 $[1,k]$，先把他们连成一条链。

然后对于任意一棵树，跑出只把 $>k$ 的数删掉的 prufer。因为 $[1,k]$ 前面不会被删。

考虑一下序列里的元素，会发现前面 $n-k-1$ 个可以乱放，删最后一个只能是 $[1,k]$。

所以总方案数为：

$$\binom{n}{k}kn^{n-k-1}$$

$$\sum_{i=2}^n (-1)^i \binom{n}{i}i^ip_1^{i-1}n^{n-i}$$