从 2024/5/4 往后开始记录捏。
T1.
给你一棵树，定义一个集合的权值为 \(\dfrac{\sum_{x\in S}V_x}{\sum_{x\in S}C_x}\)。若一个点 \(\in S\)，则其父亲也必须 \(\in S\) 并且 \(|S| = k\)。求满足条件的所有集合的最大价值。\(n,k \le 2500\)。
Solution:
注意到那一个奇妙的式子和这个奇妙的条件，我们可以联想到 \(0/1\) 分数规划。不会的出门右转。
我们定义 \(dp_{u,s}\) 为在 \(u\) 的子树下我们一共选择了整整 \(s\) 个点。
所以我们可以对于每一个儿子节点都举出他的子树中选择了多少个点然后对于所有情况取个 \(\max\) 即可的到 \(dp_{u,s}\)。然后我们在进行 \(0/1\) 分规即可。
