分数规划+树形背包。
可以根据推荐关系建出一颗树，然后如果选了一点，则该点到根上的所有点都必须选。
二分 \(mid\)，定义每个结点的权值，然后判断选 \(k+1\) 个节点的最大值是否大于 \(0\)。
设 \(f_{i,j}\) 为当前节点 \(i\)，在其子树内选了 \(j\) 个节点，最大点权和为多少。
转移方程为 \(f_{u,j}=\max(f_{u,j},f_{u,j-t}+f_{v,t})\)。
初始化为 \(f_{u,0}=0\)，\(f_{u,1}=val_u\)，其余皆为 \(-inf\)。
然后我们发现这个 DP 的复杂度貌似是 \(O(n^3)\)。
但将各种限制条件加上后就变成了 \(O(n^2)\)。本人很菜，没法证明。
所以最终复杂度为 \(O(n^2 \log n)\)。
code:
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 2500 + 5;
const db eps = 1e-5, inf = LLONG_MAX >> 1;
int k, n, fa[N], siz[N];
db s[N], p[N], val[N], f[N][N];
vector<int> adj[N];
void dfs(int u) {
siz[u] = 1; f[u][1] = val[u];
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i]; if (v == fa[u]) continue;
dfs(v); siz[u] += siz[v];
for (int j = min(k + 1, siz[u]); j > 1; --j) {
for (int k = 0; k <= min(siz[v], j - 1); ++k) {
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
}
}
}
}
bool check(db mid) {
for (int i = 0; i <= n; ++i) val[i] = p[i] - mid * s[i];
for (int i = 0; i <= n; ++i) for (int j = 1; j <= k + 1; ++j) f[i][j] = -inf;
dfs(0);
return f[0][k + 1] > 0;
}
int main() {
cin >> k >> n;
for (int i = 1; i <= n; ++i) {
scanf("%lf%lf%d", &s[i], &p[i], &fa[i]);
adj[fa[i]].push_back(i);
}
double l = 0, r = 1000;
while (r - l > eps) {
db mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.3lf\n", l);
return 0;
}