01分数规划，二分答案然后把判别式变成Σp[i]-Σs[i]*mid>=0，然后树上背包判断，设f[i][j]为在i点子树里选j个的最大收益，随便背包一下就好
最丧病的是神卡常……转移的时候要另开一个一维g来转移，然后限制<=k，因为再大就没用了，还有把max变成?:的形式……
#include<iostream>#include<cstdio>#include<cstring>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]<f[u][j]+f[e[i].to][k]?g[j+k]=f[u][j]+f[e[i].to][k]:0; ???????si[u]+=si[e[i].to]; ???????for(int j=0;j<=si[u]&&j<=m;j++) ???????????f[u][j]<g[j]?f[u][j]=g[j]:0; ???} ???for(int i=min(m,si[u]);i>=0;i--) ???????f[u][i+1]=f[u][i]+a[u]; ???si[u]++,f[u][0]=0;}bool ok(double v){//cerr<<" ????"<<v<<endl; ???for(int i=1;i<=n;i++) ???{ ???????a[i]=p[i]-s[i]*v; ???????for(int j=0;j<=n;j++) ???????????f[i][j]=-1e9; ???} ???dfs(1); ???return f[1][m]>=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;}bzoj 4753: [Jsoi2016]最佳团体【01分数规划+二分+树上背包】
原文地址：https://www.cnblogs.com/lokiii/p/9789091.html