90pts求优化

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 3007
using namespace std;

const double eps = 1e-4;
const double INF = 1e9;

struct edge
{
	int v,next;
}e[N];

int head[N],size[N],K,n,tot;
double F[N][N],s[N],p[N],sum;

void add(int u,int v)
{
	e[++tot].v = v;
	e[tot].next = head[u];
	head[u] = tot;
}

void getsize(int u)
{
	size[u] = 1;
	for(int i = head[u];i;i = e[i].next)
	{
		int v = e[i].v;
		getsize(v);
		size[u] += size[v];
	}
}

double getans(int u,double x)
{
	for(int i = 1;i <= K;i += 1)
		F[u][i] = -INF;
	F[u][0] = 0;	
	F[u][1] = p[u] - s[u] * x;
	for(int i = head[u];i;i = e[i].next)
	{
		int v = e[i].v;
		getans(v,x);
		for(int j = min(size[u],K);j >= 2;j -= 1)
			for(int k = 1;k <= min(size[v],j - 1);k += 1)
				F[u][j] = max(F[u][j],F[v][k] + F[u][j - k]);
	}
}

double two_fen()
{
	double l = 0;
	double r = sum;
	double ans;
	while(r - l > eps)
	{
		double mid = (l + r) * 0.5;
		getans(0,mid);
		ans = F[0][K];
		if(ans < 0)r = mid;
		else l = mid;
	}
	return l;
}

int main()
{
	scanf("%d%d",&K,&n);
	K++;
	for(int i = 1,fa;i <= n;i += 1)
	{
		scanf("%lf%lf%d",&s[i],&p[i],&fa);
		add(fa,i);
		sum += p[i] / s[i];
	}
	getsize(0);
	printf("%.3lf\n",two_fen());
	return 0;
}