CF1917F 题解

· · 题解

题意：

给定 d 和长为 n 的数列 l，要求构造一个 n + 1 个节点的树，第 i 条边的长度为 l_i，满足这棵树的带权直径为 d。

# 分析： 首先给 $l$ 从小到大排序。 * 性质 1：如果序列最大的两个值的和大于 $d$（即 $l_n + l_{n - 1} > d$），则一定无解。 证明：一定存在一条跨过这两条边的路径，使得这条路径的和大于 $d$。 * 性质 2：如果存在 $l$ 的一个子集 $S$，使得 $S$ 的和为 $d$，并且 $l$ 的最大值在 $S$ 集合内（即存在 $S \subseteq l,\sum\limits_{i \in S} l_i = d,n \in S$），则一定有解。 证明：可以构造一条长为 $|S|$ 的链，然后把 $(1,2)$ 的边权设为 $l_n$，其他没有用到的边都一定有 $l_i \leq 1_n$，直接把这些边连在结点 $2$ 上即可，这些边无论怎么与已放的边组合都不会使得直径变得更大。 * 性质 3：如果存在 $l$ 的两个互不相交的子集 $s1,d2$ 使得这两个子集的和都不小于 $l_n$，并且 $s1,s2$ 的和恰好为 $d$（即存在 $s1 \subseteq l,s2 \subseteq l,s1 \cap s2 = \varnothing,(\sum\limits_{i \in s1} l_i) \geq l_n,(\sum\limits_{i \in s2} l_i) \geq l_n,(\sum\limits_{i \in s1} l_i)+(\sum\limits_{i \in s2} l_i) = d$），则一定有解。 证明：可以同上构造一条链，然后找到一个点 $u$，使得左端点到 $u$ 的边权和为 $\sum\limits_{i \in s1} l_i$，把剩下的边挂在 $u$ 上即可。 对于性质 2，直接 $O(nd)$ 跑一个背包即可。 对于性质 3，设 $dp(i,j)$ 表示第一个集合和为 $i$，第二个集合和为 $j$ 是否可以得到，也可以直接跑背包，这样做是 $nd ^ 2$ 的，由于状态是 $01$，可以直接用 $bitset$ 优化，这样时间复杂度是 $O(\frac{nd ^ 2}{w})$ 的，可以通过。 [Code](https://codeforces.com/contest/1917/submission/238851170)