树形 DP 裸题，令 \(f_{i,j}\) 表示结点 \(i\) 标了权值 \(j\)，\(i\) 子树内的最小权值和。
转移时枚举每个儿子，再枚举每种颜色，加上颜色不相同的最小 DP 值。
这样时间复杂度就是颜色数量的平方乘上 \(n\)。
有效颜色数量的上界可以参考我出的那道 Eternal Star。
考虑优化。容易发现对于一个结点来说有效的状态只有 DP 值最小的两种，因为两种不同的颜色肯定有一种能转移。
所以只要记录最小值和次小值以及它们的权值。转移分三种：
- 取所有儿子最小 DP 值对应权值中没有的最小权值。
- 取所有儿子最小 DP 值对应权值中没有的次小权值。
- 取某个儿子最小/次小 DP 值对应的权值，所有最小 DP 值对应的权值为该权值的儿子全部改取次小权值。
这显然覆盖了所有情况，时间复杂度 \(O(n)\)。
思路来自 \(r\color{red}{qy}\)。