题解：P12627 [ICPC 2025 NAC] Ornaments on a Tree

超级牛牛题。

首先考虑如果没有限制节点的重量，即对于 $\forall i$，都有 $w_i=-1$。

有一个贪心的策略显然是优的，考虑从叶子节点开始，父亲相同的节点中随机挑选一个使其值为 $K$，其余的等于 $0$，这样可以保证对于每一层，都能保证其吃满限制，肯定最优。

那么有重量限制怎么办呢？

我们可以让每个节点的限制变得不同，具体地，对于 $w_u \neq -1$，有 :

注意上述公式中的 $K$ 不是题目里给的，而是对于每个节点分别的限制。

我们保留原来从下往上递归的策略，对于每个节点，可以维护 $sum_u$ 表示自己和自己儿子节点的总限制和，然后就会发现对于没有限制的节点 $u$，其最优的重量为：

这个式子中的 $K$ 即为题目给定的初始值。

跑两次 DFS 即可，时间复杂度 $O(N)$。

代码很好写，不放了。