https://www.luogu.com.cn/problem/P4322

仅拿到10pts...样例过了

#include<bits/stdc++.h>
using namespace std;
const int N=2510;
int k,n;
vector<int> r[N];
int sz[N];
double f[N][N];
double s[N],p[N];
void dp(int l,double mid){
	f[l][1]=p[l]-s[l]*mid,sz[l]=1;
	for(int i=0;i<r[l].size();i++){
		int t=r[l][i];
		dp(t,mid);
		sz[l]+=sz[t];
		for(int j=min(sz[l],k);j>=1;j--)
			for(int x=0;x<=min(sz[t],j-1);x++)
                f[l][j]=max(f[l][j],f[l][j-x]+f[t][x]);
	}
}
bool check(double mid){
	memset(f,~0x3f,sizeof(f));
	dp(0,mid);
	return f[0][k]>=0;
}
int main(){
	cin >> k >> n;
	int st=0,pt=0;
	for(int i=1;i<=n;i++){
		int temp;
		cin >> s[i] >> p[i] >> temp;
		r[temp].push_back(i);
	}
	k++;
	double l=0,r=10000;
	while(r-l>0.0001){
		double mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.3f",l);
    return 0;
}