自动搬运

查看原文

来自洛谷，原作者为

	xiaolilsq 灰名不比红名好看（

搬运于2025-08-24 22:49:18，当前版本为作者最后更新于2023-08-03 23:51:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑 Prüfer 序列构造树的过程，从前往后扫过整个序列，记录当前度数为 $1$ 的点集 $S$，以及已经被删除的点集 $T$，每次如果遇到数 $x\not\in (S\cup T)$，那么就将 $S$ 中最小值连上 $x$，然后删除 $S$ 中的最小值将其加入 $T$，而 $x$ 则可能可以加入 $S$ 也可能不加入 $S$，序列扫完后必然 $|S|=1,|T|=n-2$，这时 $S$ 中唯一的数就会连上 $n$。

于是可以如此 dp，设 $f(i,j,S,T)$ 表示考虑 $i\sim m$ 这个序列中的子序列为最后一段，$S,T$ 为上面描述的两个点集，其中 $j$ 与 $n$ 距离的总和以及方案数。按照上面转移 $O(1)$，且 $S\cap T=\varnothing$，所以复杂度为 $O(3^nnm)$。

考虑 Prüfer 序列具体构造过程是如何从 $O(n\log n)$ 优化到 $O(n)$ 的，类似的，优化掉 $3^n$，用一个集合 $L=S\cup T$，那么实际上 $S$ 就是 $L$ 的一个后缀加上最多前面一个新加的点，所以可以将 $3^n$ 优化到 $2^nn^2$，时间复杂度复杂度优化为 $O(2^nn^3m)$。

但是我们发现如果当且 dp 要求的是 $j$ 与 $n$ 的距离，那么我们唯一关心的就是 $j$ 连出去的父亲，所以如果新加的点如果不是 $j$ 那么我们其实完全不关心它具体是谁，于是一个 $n$ 可以被优化为一个 $01$ 储存的状态，即 $S$ 中当前最小的点是否恰好为 $j$，于是时间复杂度优化为 $O(2^nn^2m)$，可以通过所有数据。