【洛谷-P4395】[BOI2003]Gem 气垫车

题意#

给出一棵 $N$ 个点的树，要求你为树上的结点标上权值，权值可以是任意的正整数。

唯一的限制条件是相邻的两个结点不能标上相同的权值。

求一种方案，使得整棵树的总价值最小，只需要输出最小价值。

$1\leq N\leq 10000$.

分析#

只用 $1/2$ 染，是错误的。

反例：

结论：用 $\log n$ 种颜色即可。于是树上背包，容易通过。