实在是卡不过了QWQ TLE #6 #10

#include<bits/stdc++.h>
using namespace std;
#define cmax(a,b) a=a>b?a:b
#define cmin(a,b) a=a<b?a:b
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)&&c!='-') c=getchar();
	if(c=='-') f=-1;
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
const int _=2502;
struct edge{
	int to,next;
}e[_<<1];
const double ex=1e-4;
int tot,k,n,h[_],sz[_];
double dp[_][_],d[_],p[_],s[_];
inline void add(int x,int y){
	e[++tot]=(edge){y,h[x]};
	h[x]=tot;
}
void dfs(int x,int fa){
	sz[x]=1,dp[x][1]=d[x];
	for(register int i=h[x];i;i=e[i].next){
		int y=e[i].to;
		if(y==fa) continue;
		dfs(y,x);
		sz[x]+=sz[y];
		for(register int j=min(k+1,sz[x]);j;j--){
			for(register int z=1;z<=min(j-1,sz[x]);z++){
				cmax(dp[x][j],dp[y][z]+dp[x][j-z]);
			}
		}
	}
}
inline bool check(double m){
	for(register int i=1;i<=n;i++){
		d[i]=p[i]-s[i]*m;
	}
	for(register int i=0;i<=n;i++){
		for(register int j=1;j<=k+1;j++){
			dp[i][j]=-2147483647;
		}
	}
	dfs(0,-1);
	return dp[0][k+1]>=0;
}
int main(){
	cin>>k>>n;
	double l=0,r=0;
	for(int i=1;i<=n;i++){
		s[i]=read(),p[i]=read();
		cmax(r,p[i]); 
		add(read(),i);
	}
	while(r-l>ex){
		double mid=(l+r)/2;
		if(check(mid)){
			l=mid;
		}else{
			r=mid;
		}
//		printf("l=%lf r=%lf\n",l,r);
	}
	printf("%.3lf",l);
	return 0;
}