P4395 [BOI2003] Gem 气垫车

树形 DP 裸题，令 \(f_{i,j}\) 表示结点 \(i\) 标了权值 \(j\)，\(i\) 子树内的最小权值和。

转移时枚举每个儿子，再枚举每种颜色，加上颜色不相同的最小 DP 值。

这样时间复杂度就是颜色数量的平方乘上 \(n\)。

有效颜色数量的上界可以参考我出的那道 Eternal Star。

考虑优化。容易发现对于一个结点来说有效的状态只有 DP 值最小的两种，因为两种不同的颜色肯定有一种能转移。

所以只要记录最小值和次小值以及它们的权值。转移分三种：

• 取所有儿子最小 DP 值对应权值中没有的最小权值。
• 取所有儿子最小 DP 值对应权值中没有的次小权值。
• 取某个儿子最小/次小 DP 值对应的权值，所有最小 DP 值对应的权值为该权值的儿子全部改取次小权值。

这显然覆盖了所有情况，时间复杂度 \(O(n)\)。

思路来自 \(r\color{red}{qy}\)。