题解：CF1205D Almost All

· · 题解

Almost All

首先吐槽一嘴，这个数据范围很奇怪，这题是可以做到 O(n) 的，可是 n\leq 1000。这什么神操作？

先不管数据范围以及题目的要求。拿到这题，首先按照题意随意构造几个。如果是一条长度为 n 的链，若边权全为 1 则可以构造出 [0, n-1]。瞄一眼所求，发现是一个二次的式子，于是想到把这条链看作左右两段，想办法让它们乘起来，我们可以类似进制的操作。先按照前面所述的方法，设左边构造出 [0, a]，右边构造出 [0, b]，此时，将右边的边权全部乘上 a+1，则右边变成了 0, a+1, 2(a+1), \dots, b(a+1)，再加上左边 [0, a]，则可以构造出 [0, ab+a+b] 的数。当然如果分成更多段，当 n 大的时候可以做得更好，不过在此题没有必要。

再回过头看看题目要求，把 \left\lfloor\frac{2n^2}{9}\right\rfloor 中的 \frac{2n^2}{9} 看成 \frac{n}{3}\times\frac{2n}{3}，则在一条链的情况，只需要把链分成长度比为 \frac{1}{2} 的两段，当然比离 1 越近越好，就可以达到题目要求。那么，对于一般情况，只需要把整棵树拆成两棵分别用链的方法解决。

而对于单独一棵的贡献，若要从链的方法迁移，则能产生贡献的就是树上的节点到树根的链。比如操作子树 u 时，对于两棵子树 v1, v2，设子树 v1 可以做出 [0, a]，子树 v2 可以做出 [0, b]。设边 (u, v1) 的边权为 w（这是因为 v1 以前的子树已经表示出了 [0, w-1]），则子树 v1 实际表示出了 [w, w+a]。那么给子树 v2 的值都加上 w+a+1，即将 (u, v2) 的边权设为 w+a+1，就可以最大化表示出的数的数量了。可以发现，一棵子树 u 能产生的贡献为 size_u-1，这个使用归纳法可证。则像做链的方法一样把子树 u 分成两部分即可。

为了方便划分这两部分，可以先求出树的重心，此时将重心作为根，则每棵子树的大小都不超过 \left\lfloor\frac{n}{2}\right\rfloor，把子树按大小降序排，按顺序取子树，当取的总大小不小于 \left\lfloor\frac{n}{3}\right\rfloor 为止，则一定能分成大小差不超过 \left\lfloor\frac{n}{3}\right\rfloor 的两部分。

代码在此。