看到双倍经验我立马打开了题解通道。
思路
看到这一类某个数除以某个数的题容易联想到分数规划。
我们可以每个点和他的推荐人之间连边（双向），接着以 \(p_i - s_i * mid\) 为点权跑动态规划即可。
设 \(f_{i, j}\) 表示从 \(i\) 的子树中选 \(j\) 个节点的最大总价值，\(si_i\) 表示当前节点 \(i\) 处理了的节点数。
则转移式为 \(f_{u, i + j} = \max(f_{u, i} + f_{v, j})\)。
同时，由于只有当推荐人也属于团队或者是 CEO 时，你才能将候选人分配到团队中，当前的 \(f_{u, i}\) 一定选了 \(u\)，所以我们要把 \(f_{u，i}\) 全部向左移一位，同时加上 \(c_i\)（点权）。
代码
#include <bits/stdc++.h>
#define il inline
#define pii pair<int, int>
#define ppp(QWQ, QAQ) pair<QWQ, QAQ>
#define pb emplace_back
#define pf emplace_front
#define mpa make_pair
#define pqs(QWQ) priority_queue<QWQ, vector<QWQ>, greater<QWQ> >
#define pqb(QWQ) priority_queue<QWQ>
#define Rep(i, s, e, t) for(int i = (s); i <= (e); i += (t))
#define REP(i, s, e, t) for(int i = (s); i >= (e); i -= (t))
#define debug(a, b) cout << #a << " = " << a << b;
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) (a) = ((a) < (b) ? (a) : (b))
#define Max(a, b) (a) = ((a) > (b) ? (a) : (b))
#define fi first
#define se second
#define int ll
using namespace std;
using ll = long long;
using ull = unsigned long long;il ll read() { ll a = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9') { a = a * 10 + ch - '0'; ch = getchar(); } return a * f; }
il void write(ll x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); }const int N = 2510;
const double eps = 1e-5, INF = 1e18;
int k, n, si[N], a[N], b[N];
double c[N], f[N][N], g[N];
vector<int> e[N];il void add(int u, int v) { e[u].pb(v); }il void dfs(int u, int fa) {Rep(i, 1, n, 1) f[u][i] = -INF;f[u][0] = si[u] = 0;for(auto &v : e[u]) {if(v == fa) continue;dfs(v, u);fill(g, g + n + 1, -INF);Rep(i, 0, si[u], 1) Rep(j, 0, si[v], 1) Max(g[i + j], f[u][i] + f[v][j]);Rep(i, 0, si[u] + si[v], 1) f[u][i] = g[i];si[u] += si[v];}REP(i, si[u], 0, 1) f[u][i + 1] = f[u][i] + c[u];//强制选择节点 u 本身++si[u];//选了的节点
}il bool check(double x) {Rep(i, 1, n, 1) c[i] = b[i] - a[i] * x;dfs(0, -1);return f[0][k + 1] >= 0;
}signed main() {k = read(), n = read();Rep(i, 1, n, 1) {a[i] = read(), b[i] = read();int u = read();add(u, i), add(i, u);}double l = 0, r = 1e4;while(r - l > eps) {double mid = (l + r) / 2;if(check(mid)) l = mid;else r = mid;}printf("%.3f", l);return (1 ^ 0 ^ 1);
}