自动搬运

查看原文

来自洛谷，原作者为

	Imakf **

搬运于2025-08-24 22:44:02，当前版本为作者最后更新于2023-02-01 13:53:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

咋青山老师的题都没人写题解，伤心了啊。

$d=2$ 部分分

先考虑部分分 $d=2$，要求操作两次把树还原成一条链。

其实任意链本质上与 $1-2-3-\cdots-n$（下文称“排好序的链”）没区别，因为可以对编号重新映射。

先考虑什么情况下可以一次操作把把树变成排好序的链。

有一种比较好的情况是：当前树恰好是对序列建立出的大根笛卡尔树，此时由于删去最小值之后，剩余结点最小值依然在叶子位置，所以我们依次连接最小值就可得到所需链。

于是不难发现：只要树满足“删去最小值之后，剩余结点最小值依然在叶子位置”，即可实现一次操作还原成排好序的链。

那么怎么一次操作变成满足这样条件的树呢，那就直接点分治的时候，每次都选子树内权值最大的作为分治中心就行了。

获得 20 分！

正解

考虑怎么做整道题。

先把 $T$ 变成 $d=2$ 的链 $T_1$，$S$ 由某条链 $T_1$ 变来其中每一次操作都使最大度数 $+1$，发现要操作 $n$ 次，非常好。

已经解决 $T\to T_1$，考虑怎么解决 $T_1 \to S$。

把过程反过来考虑，$S$ 的上一个状态是什么，然后尝试减小 $S$ 的最大度点的度数。

你发现有一种方法如下：

选 $S$ 的一个叶子结点为根，然后 dfs 整棵树，如果 $u$ 的某个孩子 $v$ 为当前最大度数 $d$，则删去边 $(u,v)$，再在 $v$ 子树中随便选一个叶子 $w$，然后连接 $(u,w)$。可以说明 $w$ 一定存在，因为二度点不需要管，缩完二度点后，显然叶子比其他所有点数量都多。维护子树内的所有叶子可以链表。

注意到我们必须先通过 $T_1 \to S$ 求出 $T_1$，然后再进行 $T\to T_1$，所以说要存下中途的操作再逆序输出。

复杂度 $O(nd+n\alpha (n))$。

代码写得比较丑，就不放了。