很厉害的题，记录下
题意是随机一棵无根树，随一个根，每条边存在（能走通）的概率为 \(p\)，以根为起点，每次一方选择当前点的一个能走通的儿子走过去，问先手必胜的概率.
容易发现可以当成有根树.
用 \(F(x)\) 和 \(G(x)\) 表示必胜树和必败树的 egf，有
\[\begin{cases} F(x) = xe^{F(x)}\left(e^{G(x)}-1\right)\\ G(x) = xe^{F(x)} \end{cases} \]记有根树的 egf 为 \(T(x)\)，根据经典结论有 \(T(x) = \sum_{i\ge 1}\dfrac{n^{n-1}}{n!}x^n\)，记其复合逆为 \(H(x) = xe^{-x}\).
由 \(T(x) = F(x) + G(x)\)，得 \(T(x) = G(x)e^{G(x)} = -H(G(x))\)，于是 \(G(x) = -T(-T(x))\).
答案为
\[1 - \frac{n!}{n^{n-1}}[x^n]\frac1p G\left(pxe^{(1-p)T(x)}\right) \]而
\[[x^n]G\left(pxe^{(1-p)T(x)}\right) = [x^n]G\left(pT(x)e^{-pT(x)}\right) = [x^n]G(H(pT(x))) = [x^n]-T(-T(H(pT(x)))) = [x^n]-T(-pT(x)) \]接下来考虑求 \([x^n]T(-pT)\)，先展开一层
\[\begin{split} [x^n]T(-pT) &=[x^n]\sum_{i\ge 1} \frac{i^{i-1}}{i!}(-pT(x))^i\\ &=\sum_{i\ge 1} \frac{i^{i-1}}{i!}(-p)^i[x^n]T^i(x) \end{split} \]考虑求 \([x^n]T^i(x)\)，施 Lagrange 反演
\[[x^n]T^i(x) = \frac{i}{n}[x^{n-i}]e^{nx} = \frac{i}{n}\frac{n^{n-i}}{(n-i)!} \]代入得
\[[x^n]T(-pT) = \sum_{i\ge 1} \frac{(-pi)^i n^{n-i-1}}{i!(n-i)!} \]那么答案为
\[1 + \frac1p\sum_{i\ge 1}\binom{n}{i}\left(\frac{-ip}{n}\right)^i \]到这里，这道题就结束了，然而...
如此优美的题目，想必有组合意义吧！
考虑对必败树计数，必败树根的所有子树一定均为必胜树，容斥为 所有树的方案数-钦定为必败树的方案数，于是加入每棵子树时分是否钦定两种情况分别加入，被钦定的结点可以继续钦定其孩子. 那么所有被钦定的结点形如一棵树，每个被钦定的结点又和其下面挂的所有未被钦定的结点构成一颗树，那么形如一个 \(n\) 个点 \(k\) 棵树的森林被一棵 \(k\) 个结点的树串了起来，这与 \(G(x) = -T(-T(x))\) 相对应. 每条边存在的概率为 \(p\)，在该容斥里的意义即为：除根结点外，一个点可以被钦定的概率为 \(p\)，于是带上概率后的必败树的 GF 即为 \(-\frac1p T(-pT(x))\).
（感觉直接想到组合意义的有点外星人了）
标签：结点,right,frac,pT,题解,钦定,ge,取胜 From： https://www.cnblogs.com/0922-Blog/p/-/just-useless-algo