传送门

解题思路

　　一道0/1分数规划+树上背包，两个应该都挺裸的，话说我常数为何如此之大。。不吸氧洛谷过不了啊。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int MAXN = 2505;

const double eps = 1e-6;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int n,k,s[MAXN],p[MAXN],head[MAXN],cnt;

int to[MAXN<<1],nxt[MAXN<<1];

double f[MAXN][MAXN],ans;

inline void add(int bg,int ed){

	to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}

int dfs(int x,int fa,double lim){

	f[x][0]=0;

	int sum=1,u;

	for(register int i=head[x];i;i=nxt[i]){

		u=to[i];if(u==fa) continue;

		sum+=dfs(u,x,lim);

		for(register int j=sum;j>=0;j--)

			for(register int t=j;t>=0;t--)

				f[x][j]=min(f[x][j],f[u][t]+f[x][j-t]);

	}

	if(sum==1) {f[x][1]=(double)s[x]*lim-p[x];return sum;}

	for(register int j=sum;j>0;j--)

		f[x][j]=f[x][j-1]+(double)s[x]*lim-p[x];

	return sum;

}

inline bool check(double lim){

	for(int i=0;i<=n;i++)

		for(int j=0;j<=n;j++) f[i][j]=1e9;

	dfs(0,0,lim);

	return f[0][k+1]<=0?1:0;

}

int main(int argc, char const *argv[]){

	k=rd();n=rd();int x;

	for(int i=1;i<=n;i++) {

		s[i]=rd(),p[i]=rd();

		x=rd();add(i,x);add(x,i);

	}

	double l=0,r=10001,mid;

	while(fabs(r-l)>=eps){

		mid=(l+r)/2;

		if(check(mid)) {ans=mid;l=mid;}

		else r=mid;

	}

	printf("%.3lf",ans);

	return 0;

}