01分数规划，二分答案然后把判别式变成Σp[i]-Σs[i]*mid>=0，然后树上背包判断，设f[i][j]为在i点子树里选j个的最大收益，随便背包一下就好

最丧病的是神卡常……转移的时候要另开一个一维g来转移，然后限制<=k，因为再大就没用了，还有把max变成?:的形式……

#include
    
     #include
     
      #include
      
       using namespace std;const int N=2505;int m,n,h[N],cnt,si[N];double s[N],p[N],g[N],f[N][N],a[N];struct qwe{    int ne,to;}e[N];int read(){    int r=0,f=1;    char p=getchar();    while(p>'9'||p<'0')    {        if(p=='-')            f=-1;        p=getchar();    }    while(p>='0'&&p<='9')    {        r=r*10+p-48;        p=getchar();    }    return r*f;}void add(int u,int v){    cnt++;    e[cnt].ne=h[u];    e[cnt].to=v;    h[u]=cnt;}void dfs(int u){    si[u]=0,f[u][0]=0;    for(int i=h[u];i;i=e[i].ne)    {        dfs(e[i].to);        for(int j=0;j<=si[u]+si[e[i].to]&&j<=m;j++)            g[j]=-1e9;        for(int j=0;j<=si[u]&&j<=m;j++)            for(int k=0;k<=si[e[i].to]&&j+k<=m;k++)                g[j+k]
       
        =0;i--)        f[u][i+1]=f[u][i]+a[u];    si[u]++,f[u][0]=0;}bool ok(double v){//cerr<<"     "<
        
         <
         
          =0;}int main(){ m=read()+1,n=read()+1; for(int i=2;i<=n;i++) { s[i]=read(),p[i]=read(); int x=read()+1; add(x,i); } double l=0,r=1e4,ans=0; while(r-l>1e-5) { double mid=(l+r)/2; if(ok(mid)) l=mid,ans=mid; else r=mid; } printf("%.3f\n",ans); return 0;}