P4395

树形 DP 裸题，令 \(f_{i,j}\) 表示结点 \(i\) 标了权值 \(j\)，\(i\) 子树内的最小权值和。 转移时枚举每个儿子，再枚举每种颜色，加上颜色不相同的最小 DP 值。 这样时间复杂度就是颜色数量的平方乘上 \(n\)。 有效颜色数量的上界可以参考我出的那道 Eternal ......