官方题解只能做到 $O(n^4)$ / $O(n^5)$？玩的太差了。可以降到 确定性的 $O(n^2\log n)$ 时间、$O(n^2)$ 空间。关键是：每个节点只对轻子树建立二维容斥多项式，重子树保留为一维 DP，再通过卷积接上合法尾段。现有简要题解给出的复杂度确实是 $O(n^4)$。([qoj.ac][1])
下面给出完整推导和实现。
状态与容斥
记 $s_u$ 为 $u$ 的子树大小，$f_u[k]$ 为从这棵子树中选择 $k$ 个不同的点，排列成合法序列的方案数。只统计非空序列，约定 $f_u[0]=0$，答案就是 $f_1[n]$。
在节点 $u$ 处，把每个儿子的子树染成一种颜色，$u$ 自己单独作为一种颜色。一个序列合法，当且仅当：
除最后一个极长同色段外，其余极长同色段的长度都为 $1$；最后一个同色段在对应子树内合法。
必要性很直接：如果一个非末尾同色段长度至少为 $2$，那么其中相邻点的 LCA 深度大于 $\operatorname{dep}(u)$，而离开这个颜色时，相邻点的 LCA 又变成 $u$，发生下降。反过来，前面的相邻点都不同色，其 LCA 全是 $u$，只需要最后的同色段内部合法即可。
因此，一个合法序列由若干个单点和一个合法终段组成。困难在于：前面的单点不能出现同色相邻，终段前面也不能紧挨同色单点。我们对这些相邻限制做容斥。
以下用 $(a)_r=a!/(a-r)!$ 表示下降阶乘，参数不合法时视为 $0$。
对于一个大小为 $s$ 的颜色，定义两个二元多项式 $A(x,y)$、$B(x,y)$。其中 $x$ 记录选取的点数，$y$ 记录容斥缩合后产生的普通块数。
$A$ 表示这个颜色不提供终段。选出并排列 $r$ 个点，再把它们分成 $j$ 个非空块，有 $(s)*r\binom{r-1}{j-1}$ 种方法。缩合了 $r-j$ 条相邻关系，容斥符号是 $(-1)^{r-j}$；普通块的整体排列留到以后处理，因此除以 $j!$。于是 $A*{0,0}=1$，且对于 $1\le j\le r\le s$，有 $A_{r,j}=(s)_r(-1)^{r-j}\binom{r-1}{j-1}/j!$，其余系数为 $0$。
$B$ 表示这个颜色提供终段。假设对应儿子为 $v$，终段有 $t$ 个点，其方案数为 $f_v[t]$。还要选择并排列 $r-t$ 个普通点，把它们分成 $j$ 个非空普通块，以及一个可以为空、与终段前端粘在一起的部分。这样的分割有 $\binom{r-t}{j}$ 种，因而
$$ B_{r,j} =\frac1{j!}\sum_{t=1}^{r-j} f_v[t](s-t)_{r-t}(-1)^{r-t-j}\binom{r-t}{j}. $$
注意，与终段粘在一起的部分也属于容斥：它用来排除“终段前面紧挨同色单点”的情况。终段本身是一个特殊块，不计入 $y$ 的次数，而且最终必须放在整个序列末尾。
这个式子不能直接三重循环计算。令 $a_t=f_v[t](s-t)!$，并定义 $C_0(y)=0$、$C_r(y)=(y-1)C_{r-1}(y)+a_r$，则 $C_r(y)=\sum_{t=1}^r a_t(y-1)^{r-t}$，所以 $B_{r,j}=[y^j]C_r(y)/((s-r)!j!)$。逐行维护 $C_r$，就能在 $O(s^2)$ 时间内构造整个 $B$。
现在取 $u$ 的最大儿子为重儿子 $H$，记其大小为 $h$；没有儿子时取 $h=0$。其余儿子以及 $u$ 自己统称为轻侧，轻侧总大小为 $b=s_u-h$。
只合并轻侧的多项式，不构造重儿子的二维多项式。
用 $(P,Q)$ 表示已经合并的颜色：$P$ 表示没有颜色提供终段，$Q$ 表示恰好一个颜色提供终段。两个部分的合并是 $(P_1P_2,\ Q_1P_2+P_1Q_2)$。节点 $u$ 自己对应 $(1+xy,x)$。
于是，合并完成后，$P_{j,r}$ 记录轻侧选出 $j$ 个点、形成 $r$ 个普通块的容斥权重；$Q_{j,r}$ 记录轻侧选出 $j$ 个点、形成 $r$ 个普通块和一个特殊终段的容斥权重。
转移与复杂度优化
接下来把重儿子的点插入轻侧形成的块之间。重儿子的普通点也都必须单独成段，所以每个空隙最多插入一个。
如果终段来自重儿子，将其固定在最后。轻侧的 $r$ 个普通块有 $r!$ 种排列，在终段之前共有 $r$ 个可插入空隙。因此插入 $m$ 个重儿子普通点的系数为 $\binom rm$。
如果终段来自轻侧，则有 $r$ 个普通块和一个固定在最后的特殊块，共有 $r+1$ 个可插入空隙，对应系数为 $\binom{r+1}m$。
定义
$$ X_{j,m}=\sum_r P_{j,r}r!\binom rm, \qquad Y_{j,m}=\sum_r Q_{j,r}r!\binom{r+1}m. $$
终段来自轻侧时，重儿子的 $m$ 个普通点可以按 $(h)_m$ 种方式选择和排列。终段来自重儿子时，先选择一个长度为 $t$ 的合法终段，再从剩下的点中选取并排列 $m$ 个普通点，有 $f_H[t](h-t)_m$ 种方法。完整转移就是
$$ f_u[k] =\sum_{j+m=k}Y_{j,m}(h)_m +\sum_{\substack{j+m+t=k\\t\ge1}} X_{j,m}f_H[t](h-t)_m. $$
没有重儿子时，第二项为空。
这个转移看起来仍然有很多层循环，但都可以用卷积消掉。
首先考虑变换 $T(a)*m=\sum*{r\ge m}a_r r!\binom rm$。展开组合数，得到 $T(a)*m=\frac1{m!}\sum*{r\ge m}a_r(r!)^2/(r-m)!$。把序列 $a_r(r!)^2$ 翻转，与 $1/r!$ 卷积，就能在 $O(d\log d)$ 时间内算出一整行。
对 $P$ 的每一行进行这个变换即可得到 $X$。对 $Q$ 的每一行得到 $E$ 后，由 $\binom{r+1}m=\binom rm+\binom r{m-1}$，可知 $Y_{j,m}=E_{j,m}+E_{j,m-1}$。所以计算所有 $X,Y$ 只需 $O(b^2\log b)$ 时间。
再考虑第二项。令 $G[t]=f_H[t](h-t)!$。固定轻侧选点数 $j$，设 $R=m+t$，那么这一行对 $f_u[j+R]$ 的贡献就是 $(X_j*G)[R]/(h-R)!$。每个 $j$ 只需要一次一维卷积，总时间为 $O(bs_u\log s_u)$。
剩下的问题是如何快速合并轻侧的二元多项式。合并后总大小为 $w$ 时，使用代换 $x^iy^j\mapsto z^{i(w+1)+j}$。因为乘积中 $y$ 的次数不超过 $w$，不会发生串位，所以一次二元乘法可以转化为长度 $O(w^2)$ 的一元卷积，耗时 $O(w^2\log w)$。
合并顺序不能随意选择。实现中每次取大小最小的两个部分合并，即采用 Huffman 式合并。沿着这种合并树，每上升两层，子树权重至少翻倍，因此所有合并节点的权重平方之和为 $O(b^2)$。于是轻侧全部合并的时间为 $O(b^2\log b)$。
综上，一个节点的总时间为 $O(s_u b_u\log s_u)$。而由于 $h$ 是最大儿子的大小，有 $\sum_{v\in\operatorname{ch}(u)}s_v^2\le h(s_u-1)$，所以 $s_u b_u\le s_u^2-\sum_{v\in\operatorname{ch}(u)}s_v^2$。对所有节点求和，右侧望远镜消去，得到 $\sum_u s_u b_u\le n^2$。
因此，总复杂度为 $O(n^2\log n)$ 时间、$O(n^2)$ 空间。这里对链状树也成立：不会在每个祖先处重新构造重儿子的二维表。