月 题解

· · 题解

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

因此我们不妨在构造过程中尽可能地最小化该树的最大深度。若我们最终构造出的最大深度为 d，因此我们可以得出一定不存在长度不大于

同时我们可以知道满足最大深度为 $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)$，瓶颈在于排序。