Code

#include <iostream>
#include <vector>
using namespace std;
const int N=2510;
int n,k,u,siz[N];
double s[N],p[N],a[N];
double ans,dp[N][N];
vector <int> g[N];
void dfs(int x,int fa){
	dp[x][1]=a[x];siz[x]=1;
	for(int i=0;i<g[x].size();++i){
		int y=g[x][i];
		if(y==fa) continue;
		dfs(y,x);
		siz[x]+=siz[y];
		for(int j=min(siz[x],k+1);j>=1;--j){
			for(int ol=0;ol<=min(siz[y],j-1);++ol){
				dp[x][j]=max(dp[x][j],dp[x][j-ol]+dp[y][ol]);
			}
		}
	}
}
bool check(double mid){
	a[0]=0;
	for(int i=1;i<=n;++i) a[i]=p[i]-s[i]*mid;
	for(int i=0;i<=n;++i){
		for(int j=1;j<=k+1;++j){
			dp[i][j]=-1e9;
		}
	}
	dfs(0,-1);
	return dp[0][k+1]>=0;
}
signed main(){
	scanf("%d%d",&k,&n);
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%d",&s[i],&p[i],&u);
		g[u].push_back(i);
	}
	double l=0,r=10000;
	while(l<r-1e-4){
		double mid=(l+r)/2;
		if(check(mid)){
			l=mid+1;
			ans=mid;
		}
		else r=mid-1;
	}
	printf("%.3lf",ans);
	return 0;
}

样例输出0.000。