【题意】n个人，每个人有价值ai和代价bi和一个依赖对象ri<i，选择 i 时 ri 也必须选择（ri=0时不依赖），求选择k个人使得Σai/Σbi最大。n<=2500，ai,bi<=1e4。
【算法】01分数规划+树上背包
【题解】首先二分答案ans，根据01分数规划赋新的权值ci=ai-ans*bi，转化为是否能在树上找k个点使得权值和>=0。
设f[i][j]表示子树 i 选择 j 个点的最大权值和，然后做树上背包即可。
注意：第一维从大到小枚举j，第二维枚举儿子背包。这个背包比较特殊，是因为一批物品只能也必须取一个。
两个节点只在它们LCA处计算一次，所以只要背包不枚举满，均摊复杂度就是N^2。
总复杂度O(n^2*log ai)。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
const double inf=-; int first[maxn],n,K,a[maxn],b[maxn],tot,sz[maxn];
double f[maxn][maxn],c[maxn];
struct edge{int v,from;}e[maxn];
void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
double max(double a,double b){return a<b?b:a;}
void dfs(int x){
for(int i=;i<=K;i++)f[x][i]=inf;
if(x)f[x][]=c[x],sz[x]=;else f[x][]=;
for(int i=first[x];i;i=e[i].from){
dfs(e[i].v);sz[x]+=sz[e[i].v];
for(int k=min(K,sz[x]);k>=;k--)//
for(int j=min(k-(x!=),sz[e[i].v]);j>=;j--)if(f[x][k-j]>inf+){
f[x][k]=max(f[x][k],f[x][k-j]+f[e[i].v][j]);
}else break;
}
}
bool solve(double ans){
for(int i=;i<=n;i++)c[i]=1.0*a[i]-ans*b[i];
dfs();
return f[][K]>=;
}
int main(){
scanf("%d%d",&K,&n);
double l=,r=,mid;
for(int i=;i<=n;i++){
int fa;
scanf("%d%d%d",&b[i],&a[i],&fa);
insert(fa,i);
}
r=1e4;//？
while(r-l>1e-){
mid=(l+r)/;
if(solve(mid))l=mid;else r=mid;
}
printf("%.3lf",l);
return ;
}