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

· · 题解

超级牛牛题。

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

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

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

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

K_u=K_{old} -w_u;K_{fa(u)}=K_{fa(u),old} - w_u

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

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

w_{u,new}=\min(K-sum_u,K-sum_{fa(u)})

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

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

代码很好写，不放了。