题目概述

有 $n+1$ 个人，选第 $i$ 个人需要花费 $s_i$ ，得到 $p_i$ 的贡献，第一个人必选，没有花费和贡献。$2\sim n+1$ 都有一个推荐人（推荐人编号小于自己的编号），一个人选了就必须选推荐人，求最大性价比。

解题报告

先分数规划，然后转为树形DP。定义 $f[i][j]$ 表示 $i$ 子树中选了 $j$ 个人的最优解，瞎转移就行了。

注意转移时需要默认 $i$ 是必选的，所以 $f[i][0]$ 刚开始没有值，处理完树形背包之后再把 $f[i][0]$ 给 $0$（或者再开一个数组，没人拦着你）。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long double DB;
const int maxn=2500;

int K,n,w[maxn+5],p[maxn+5],si[maxn+5];DB P[maxn+5];
int E,lnk[maxn+5],nxt[maxn+5],son[maxn+5];DB f[maxn+5][maxn+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void DP(int x){
    memset(f[x],254,sizeof(f[x]));f[x][1]=P[x];si[x]=1;
    for (int e=lnk[x],u;e;si[x]+=si[u],e=nxt[e])
        for (int j=(DP(u=son[e]),min(si[x]+si[u],K));j;j--)
            for (int i=max(j-si[x],0);i<j&&i<=si[u];i++) //这么写就O(n^2)啦
                f[x][j]=max(f[x][j],f[x][j-i]+f[u][i]);f[x][0]=0;
}
inline bool check(DB ans) {P[1]=0;for (int i=2;i<=n;i++) P[i]=p[i]-ans*w[i];DP(1);return f[1][K]>1e-8;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=2,fa=(scanf("%d%d",&K,&n),K++,n++);i<=n;i++)
        scanf("%d%d%d",&w[i],&p[i],&fa),Add(fa+1,i);
    DB L=0,R=25000000,mid;while (R-L>1e-5) check(mid=(L+R)/2)?L=mid:R=mid;
    return printf("%.3f\n",(double)L),0;
}