题解：CF2122G Tree Parking

计数基本功题。当然如果你直接贺 poly 板子求欧拉数了那我也没话说。

首先考虑对于一棵固定的树求答案：

可以考虑树形 dp，设 $f_u$ 表示 $u$ 子树的方案数。那么转移时，我们可以任意内部排列所有子树的区间，最后再插入 $u$ 的区间。

$u$ 的区间不能和其他任意一个区间相交，因此有 $2sz_u-1$ 种可行的相对位置。子树的部分就是一个多重排列，因此可以得到转移式：

可以通过考虑每个 $sz_u$ 的计算次数来化简，得到 $f_1 = \frac{(2n - 1)!}{2^{n-1}\prod \limits_{v\neq 1} sz_v}=\frac{(2n)!}{2^n\prod\limits_{v}sz_v}$。

考虑 $\prod\frac{1}{sz_v}$ 的组合意义。我们知道 $\frac{n!}{\prod sz_v}$ 表示树的拓扑序个数，因此我们可以枚举所有可能的拓扑序，计算合法的树的数量，求和后除以 $n!$。而这里所有的 $1$ 开头的拓扑序都是等价的，所以有 $(n-1)!$ 种对称情况，因此最后只需要乘上 $\frac{1}{n}$。

固定拓扑序的情况下计算树的个数是容易的，我们只需要按照拓扑序插入所有的点。设 $dp_{n, k}$ 表示 $n$ 个点的树有 $k$ 个叶子的方案数。那么有转移式 $dp_{n, k} = (n - k) dp_{n - 1, k - 1} + kdp_{n - 1, k}$，两项分别表示把第 $n$ 个点接在叶子下面还是接在根下面。

容易与欧拉数的组合意义建立双射：$dp_{n, k}$ 实际上就是长度为 $n-1$ 的排列，有 $k - 1$ 个相邻上升的排列数量（这里产生 $-1$ 是因为我们把根挖掉了）。

所以问题就变成了求单项欧拉数 $A(n, k)$。可以考虑二项式反演，设 $g_t$ 表示钦定 $t$ 个上升的方案数，那么会形成 $n-t$ 段，每段内部唯一。

这里可以用 EGF 解决，以凑出多重排列的系数：也就是要求 $[x^n](e^x-1)^{n-t}$，因为每段非空。进行展开：

再做二项式反演：答案 $=\sum\limits_{t = k}^{n - 1}\binom{t}{k}(-1)^{t-k}g_t$，带入化简：

合并 $-1$ 的幂并交换求和号：

后面这个组合数求和可以这样考虑：$\binom{t}{k}$ 是 $\frac{1}{(1-x)^{k + 1}}$ 的 $x^{t - k}$ 次项系数，$\binom{n-t}{i}$ 是 $\frac{1}{(1-x)^{i + 1}}$ 的 $x^{n-t-i}$ 次项系数。所以乘起来求和就是 $\frac{1}{(1-x)^{i+k+2}}$ 的 $x^{n-k-i}$ 次项系数，即 $\binom{n + 1}{i + k + 1}$。

因此所求为 $=\sum\limits_{i = 1} ^{n - k} i ^n(-1)^{n - k - i}\binom{n + 1}{i + k + 1}$。

最终答案为：

$\mathcal O(n)$ 计算即可。