自动搬运

查看原文

来自洛谷，原作者为

	User_Unauthorized AFO

搬运于2025-08-24 23:00:11，当前版本为作者最后更新于2024-04-06 19:50:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先我们有如下两条结论：

• 对于任意一棵最大深度为 $d$ 的有根树，其直径长度不大于 $2 \times d$。

• 若某棵树的直径长度为 $l$，那么取直径中点为根可以得到最大深度为 $\lceil\frac{l}{2}\rceil$ 的有根树。

因此我们不妨在构造过程中尽可能地最小化该树的最大深度。若我们最终构造出的最大深度为 $d$，因此我们可以得出一定不存在长度不大于 $2 \times (d - 1)$ 的直径。否则我们可以得到一棵最大深度为 $d - 1$ 的有根树，与最小的构造不符。

同时我们可以知道满足最大深度为 $d$ 的树一定满足直径长度为 $[2 \times d - 1, 2 \times d]$。因此我们考虑该树直径长度能否取到 $2 \times d - 1$，发现此种情况当且仅当该树根节点仅有一个儿子节点的子树内的节点最大深度为 $d$，其余儿子节点子树内的节点最大深度均为 $d - 1$。同时可以发现第 $d$ 层中的节点一定均为度数为 $1$ 的叶子节点，因此问题转化为了能否最大化一棵子树的叶子节点数量。

考虑如下构造方法：将所有节点按度数降序排列，从前之后依次考虑每个节点，将其连接在排列中第一个还可以被连接的节点。

我们按照上述的两个要求证明此构造方案的合理性。

1. 要求最小化最大深度，可以发现，若存在节点 $u, v$，满足 $dep_u < dep_v$ 且 $d_u < d_v$，那么交换 $u, v$ 一定可以使得该树容纳更多的节点。

2. 要求尽可能地使得仅有一棵子树最大深度为 $d$，可以发现，在第一条的限制下，每一层可以填的节点都是固定的，因此将每一层度数大的节点优先填到一棵子树内一定不劣。

因此上述构造方案一定不劣。

复杂度为 $\mathcal{O}(\sum n \log n)$，瓶颈在于排序。