Date: 2015-01-19 14:47
分享一个题目和解法： 用正整数对树的节点编号，要求相邻节点的编号不同，同时编号的总和最小。
假设$n$是树的节点数，编号一个显然的上界是$n$，所以可以得到一个$O(n^2)$的dp，令$f(u, x)$表示$u$的父亲编号是$x$，$u$子树编号总和的最小值。 则$$f(u, x) = \min_{y \neq x} \sum_{v} f(v, y)$$
接下来我们证明$x$的上界是$O(\sqrt{n})$，就可以得到一个$O(n^{2/3})$的算法。 因为树是二分图，总可以用两种颜色染色，由对称性，$2$的数量不会超过一半，所以这种方案的总和不超过$\frac{3}{2} n$。 假设编号的最大值是$x$，则$1, 2, \dots, x$一定都存在，方案的总和至少是$$1 + 2 + \dots + x = \frac{(1 + x)x}{2} \leq \frac{3}{2}n \implies x = O(\sqrt{n})$$
另一方面，我们考虑原来的dp，我们发现对于固定的$u$，$f(u, 1), f(u, 2), \dots, f(u, n)$至多只有$2$个值，更加确切的说，有$(n - 1)$个是$\min_y \sum_{v} f(v, y)$，另外一个是$\sum_{v} f(v, y)$的次小值。所以，我们可以用$3$个数来表示这$n$个结果。 在转移的时候，假设点$u$有$k$个儿子，那么只会有$2k$个特殊点，所以总复杂度是$O(n)$的。