https://www.lydsy.com/JudgeOnline/problem.php?id=4753
JSOI信息学代表队一共有N名候选人，这些候选人从1到N编号。方便起见，JYY的编号是0号。每个候选人都由一位编号比他小的候选人Ri推荐。如果Ri=0则说明这个候选人是JYY自己看上的。为了保证团队的和谐，JYY需要保证，如果招募了候选人i，那么候选人Ri"也一定需要在团队中。当然了，JYY自己总是在团队里的。每一个候选人都有一个战斗值Pi"，也有一个招募费用Si"。JYY希望招募K个候选人（JYY自己不算），组成一个性价比最高的团队。也就是，这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大。
01分数规划裸题，二分答案w，每个点点权为p[i]-w*s[i]，判断最大值是否>0即可。
显然是树型背包问题，由于看不懂什么神奇的刷表法，我还是写的复杂度我不会证的dfs。
于是我人傻自带大常数硬生生把傻逼题写成神题……
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double dl;
const int INF=1e7;
const int N=;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int to,nxt;
}e[N*];
int cnt,k,n,s[N],p[N],head[N],sz[N];
dl dp[N][N],w[N];
inline int add(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
void dfs(int u){
for(int i=;i<=k;i++)dp[u][i]=-INF;
if(u)dp[u][]=w[u],sz[u]=;
else dp[u][]=,sz[u]=;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;dfs(v);
int len=u?:;
for(int j=min(k,sz[u]);j>=len;j--)
for(int l=;l<=min(k-j,sz[v]);l++)
dp[u][j+l]=max(dp[u][j+l],dp[u][j]+dp[v][l]);
sz[u]+=sz[v];
}
}
bool pan(dl W){
for(int i=;i<=n;i++)w[i]=(dl)p[i]-W*s[i];
dfs();
return dp[][k]>;
}
int main(){
k=read(),n=read();
for(int i=;i<=n;i++){
s[i]=read(),p[i]=read();
add(read(),i);
}
dl l=,r=1e4;
for(int i=;i<=;i++){
dl mid=(l+r)/;
if(pan(mid))l=mid;
else r=mid;
}
printf("%.3lf\n",l);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++