它 WA 了 #3……并且跑得比其他人慢多了……

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int k,n,tag,s[2510],p[2510],r[2510],order[2510],size[2510];
double left,right,f[2510][2510];
vector<int>node[2510];
inline void read(int &x)
{
	char t=getchar();
	while(!isdigit(t))
		t=getchar();
	while(isdigit(t))
	{
		x=x*10+t-'0';
		t=getchar();
	}
	return;
}
void build(int x)
{
	size[x]=1;
	for(register int i=0;i<node[x].size();++i)
	{
		build(node[x][i]);
		size[x]+=size[node[x][i]];
	}
	order[++tag]=x;
	return;
}
bool check(double x)
{
	memset(f,-0x3f,sizeof f);
	for(int i=1;i<=tag;++i)
	{
		f[i][0]=0;
		for(register int j=k+1;j>0;--j)
			f[i][j]=max(f[i-size[order[i]]][j],f[i-1][j-1]+p[order[i]]-s[order[i]]*x);
	}
	return f[tag][k+1]>=0;
}
int main()
{
	read(k);
	read(n);
	for(register int i=1;i<=n;++i)
	{
		read(s[i]);
		read(p[i]);
		read(r[i]);
		right+=p[i];
		node[r[i]].push_back(i);
	}
	build(0);
	while(fabs(left-right)>1e-6)
	{
		double mid=(left+right)/2;
		if(check(mid))
			left=mid;
		else right=mid;
	}
	printf("%.3lf",left);
	return 0;
}
//sum(p[i])/sum(s[i])>=ans
//sum(p[i]-s[i]*ans)>=0