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$。