一、问题

题目描述

JSOI 信息学代表队一共有 NNN 名候选人，这些候选人从 111 到 NNN 编号。方便起见，JYY 的编号是 000 号。每个候选人都由一位编号比他小的候选人RiR_iRi​ 推荐。如果 Ri=0R_i = 0Ri​=0​，则说明这个候选人是 JYY 自己看上的。

为了保证团队的和谐，JYY 需要保证，如果招募了候选人 iii，那么候选人 RiR_iRi​ 也一定需要在团队中。当然了，JYY 自己总是在团队里的。每一个候选人都有一个战斗值 PiP_iPi​ ，也有一个招募费用 SiS_iSi​ 。JYY 希望招募 KKK 个候选人（JYY 自己不算），组成一个性价比最高的团队。也就是，这 KKK 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。

输入格式

输入一行包含两个正整数 KKK 和 NNN 。

接下来 NNN 行，其中第 iii 行包含三个整数 SiS_iSi​ , PiP_iPi​ , RiR_iRi​ ,
表示候选人 iii 的招募费用，战斗值和推荐人编号。

输出格式

输出一行一个实数，表示最佳比值。答案保留三位小数。

样例 #1

样例输入 #1

1 2
1000 1 0
1 1000 1

样例输出 #1

0.001

提示

对于100%的数据满足1≤K≤N≤25001≤K≤N≤25001≤K≤N≤2500,0 000 ≤≤≤ RiR_iRi​ <<< iii

二、分析

这道题其实一眼看过去就是一个树形背包DP，但是这道题唯一特别的就是其中涉及到了分数。当我们求一个分数的最值的时候，我们通常使用的是二分。

1、分数规划

当题目中让我们求：∑ai∑bi\frac{\sum a_i}{\sum b_i}∑bi​∑ai​​的最大值的时候，我们应该怎么做呢？

不妨设：
∑ai∑bi=x\frac{\sum a_i}{\sum b_i}=x∑bi​∑ai​​=x

那么就有：
∑ai=xmax∗∑bi\sum a_i = x_{max} * \sum b_i ∑ai​=xmax​∗∑bi​

即：

∑ai−xmax∑bi=0\sum a_i - x_{max}\sum b_i=0 ∑ai​−xmax​∑bi​=0

我们可以将这几个求和融合一下：

∑(ai−x∗bi)=0\sum(a_i-x*b_i)=0 ∑(ai​−x∗bi​)=0

因此，我们可以让括号内的式子是CiC_iCi​

我们会发现一个特点∑Ci\sum C_i∑Ci​是关于xxx的单调函数，因此我们可以使用二分，而二分中的checkcheckcheck函数其实就是利用树形DP求出上面求和式的最大值，然后进行判断。

我们这里用到的二分是浮点数二分。

整个过程的时间复杂度是O(n2logn)O(n^2logn)O(n2logn)的。（树形背包DP看似是O(n3)O(n^3)O(n3)的，但实际上当我们对其上下界进行优化后，可以到达O(n2)O(n^2)O(n2)）。

2、树形DP

状态表示

f[u][j]f[u][j]f[u][j]表示在以uuu为根的树（包括uuu）中选jjj个节点，∑ci\sum c_i∑ci​的最大值。

状态转移

f[u][j]=max(f[u][j],f[u][j−q]+f[son][q])f[u][j]=max\bigg(f[u][j],f[u][j-q]+f[son][q]\bigg) f[u][j]=max(f[u][j],f[u][j−q]+f[son][q])

初末状态

f[u][1]f[u][1]f[u][1]表示选一个，所以就是f[u][1]=c[u]f[u][1]=c[u]f[u][1]=c[u]
f[u][0]f[u][0]f[u][0]表示选0个，所以就是f[u][0]=0f[u][0]=0f[u][0]=0

由于题目中选000节点不算进我们方案，但是我们在计算的时候，还是要算入我们的答案的，所以我们代码中选择的实际上是k+1k+1k+1个点。最终的状态即：f[0][k+1]f[0][k+1]f[0][k+1]

三、代码

#include
#define endl '\n'
#define INF  0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair pii;
const int N = 2500 + 10;
double f[N][N];
double p[N], s[N], c[N];
int siz[N];
vectoredge[N];
int n, k;//f[u][j] => 在以u为根的树中，选择j个点，c的和的最大值。void cal_siz(int u)
{siz[u] = 1;for(int i = 0; i < edge[u].size(); i ++){cal_siz(edge[u][i]);siz[u] += siz[edge[u][i]];}
}void dp(int u)
{f[u][0] = 0.0;f[u][1] = c[u];for(int i = 0; i < edge[u].size(); i ++ ){int son = edge[u][i];dp(son);for(int j = min(siz[u], k + 1); j >= 0; j -- )for(int q = 0; q <= min(siz[son], j - 1); q ++ ){if(f[u][j - q] == -INF || f[son][q] == -INF)continue;	f[u][j] = max(f[u][j], f[son][q] + f[u][j - q]);}}
}bool check(double mid)
{for(int i = 0; i <= n; i ++ )for(int j = 0; j <= k + 1; j ++ )f[i][j] = -INF;for(int i = 1; i <= n; i ++ )c[i] = p[i] - mid * s[i];dp(0);return f[0][k + 1] >= 0.0;
}double find()
{double l = 0.0, r = 5000;while(r - l > 1e-9){double mid = (l + r) / 2;if(check(mid))l = mid;elser = mid;// cout << l << " " << r << endl;}return l;
}void solve()
{cin >> k >> n;for(int i = 1; i <= n; i ++ ){int fa;cin >> s[i] >> p[i] >> fa;edge[fa].push_back(i);}cal_siz(0);printf("%.3lf", find());
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}