淀粉树题解

· · 题解

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

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))。

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