题目分析

我们有 $N$ 个候选人（编号 $1 \dots N$），以及一个固定的 JYY（编号 $0$）。
每个候选人 $i$ 有一个推荐人 $R_i$，如果选了 $i$，则必须选 $R_i$。
JYY 已经在团队中。
我们要选恰好 $K$ 个候选人（不含 JYY），使得：

$\frac{\sum P_i}{\sum S_i}$

最大。

思路

这是一个典型的分数规划 + 树形依赖背包问题。

1. 分数规划

设最大比值为 $x$，那么有：

$\frac{\sum P_i}{\sum S_i} \ge x$ 等价于 $\sum P_i - x \cdot \sum S_i \ge 0$ 即 $\sum (P_i - x \cdot S_i) \ge 0$

因此我们可以二分答案 $x$，然后判断是否存在一个合法选择方案（恰好 $K$ 个候选人，满足依赖关系），使得 $\sum (P_i - x \cdot S_i) \ge 0$。

2. 依赖背包

依赖关系形成一棵以 $0$ 为根的树（$R_i$ 是父节点）。
我们需要在树上做背包：
$dp[u][j]$ 表示在 $u$ 的子树中，选择 $j$ 个节点（不含 $u$ 本身）的最大 $\sum (P_i - x \cdot S_i)$ 值。

注意：选子树节点之前必须选 $u$，所以 $u$ 的权值在进入子树时已经计算。

3. 转移方式

对于节点 $u$，初始化 $dp[u][0] = 0$（不选任何子节点）。

遍历每个子节点 $v$，用分组背包的方式合并：

新 $dp[u]$ 从旧 $dp[u]$ 和 $dp[v]$ 合并：

对于 $j$ 从 $K$ 到 $0$（倒序，避免重复选取同一子树），
对于 $k$ 从 $0$ 到 \text{size}[v]（$v$ 子树中最多选的节点数），
如果 $j+k \le K$，则：

$ dp[u][j+k] = \max(dp[u][j+k], dp[u][j] + dp[v][k]) $

合并完所有子节点后，如果 $u \neq 0$，则我们可以选择 $u$ 本身，那么需要把 $u$ 的权值 $P_u - x \cdot S_u$ 加到所有状态中（因为选 $u$ 才能选它的子树，所以合并完子树后加上 $u$ 的贡献）：

对于 $j$ 从 $0$ 到 $K-1$： $ dp[u][j+1] = \max(dp[u][j+1], dp[u][j] + (P_u - x \cdot S_u)) $

注意：JYY（节点 0）不占 $K$ 名额，但必须选，所以它的权值在最后判断时单独加上。

4. 最终判断

二分检查时，我们看 $dp[0][K] \ge 0$ 是否成立。

时间复杂度

• 二分次数：$O(\log(\text{精度}^{-1}))$，一般 $50$ 次足够。
• 每次 DP：$O(N \cdot K)$，因为树形背包在限制背包大小 $K$ 时，每对节点只在 LCA 处合并一次，总复杂度 $O(NK)$。

总复杂度：$O(NK \log \text{精度}^{-1})$，在 $N,K \le 2500$ 时可行。