【题意】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
      
       #include
       
        #include
        
         using namespace std;const int maxn=2510;const double inf=-100000000000000;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
         
          =1;k--)//            for(int j=min(k-(x!=0),sz[e[i].v]);j>=1;j--)if(f[x][k-j]>inf+10){                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=1;i<=n;i++)c[i]=1.0*a[i]-ans*b[i];    dfs(0);    return f[0][K]>=0;}int main(){    scanf("%d%d",&K,&n);    double l=0,r=0,mid;    for(int i=1;i<=n;i++){        int fa;        scanf("%d%d%d",&b[i],&a[i],&fa);        insert(fa,i);    }    r=1e4;//？     while(r-l>1e-4){        mid=(l+r)/2;        if(solve(mid))l=mid;else r=mid;    }    printf("%.3lf",l);    return 0;}