4395

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

这一题很显然是需要我们猜一些结论 然后发现无法证明只写1/2 所以我们尝试找填的数的上限 假设最终的数的最大值为x，那么这个节点的周围肯定有1...x-1，一共x-1个节点 对这x-2个节点（除1外），每个节点都可以产生i-1个节点（其中i是节点的权值） 然后以此类推，不难写出一个代码 #inclu ......