标签：二分，树形DP
题目
Description
JSOI信息学代表队一共有N名候选人，这些候选人从1到N编号。
方便起见，JYY的编号是0号。每个候选人都由一位编号比他小的候选人Ri推荐。
如果Ri=0则说明这个候选人是JYY自己看上的。
为了保证团队的和谐，JYY需要保证，如果招募了候选人i，那么候选人Ri”也一定需要在团队中。
当然了，JYY自己总是在团队里的。每一个候选人都有一个战斗值Pi”，也有一个招募费用Si”。
JYY希望招募K个候选人（JYY自己不算），组成一个性价比最高的团队。
也就是，这K个被JYY选择的候选人的总战斗值与总招募总费用的比值最大。
Input
输入一行包含两个正整数K和N。
接下来N行，其中第i行包含3个整数Si,Pi,Ri表示候选人i的招募费用，战斗值和推荐人编号。
对于100%的数据满足1≤K≤N≤2500,0<”Si,Pi”≤10^4,0≤Ri<i
Output
输出一行一个实数，表示最佳比值。答案保留三位小数。
Sample Input
1 2
1000 1 0
1 1000 1
Sample Output
0.001
题意
给定一棵N个节点的树和每个节点的花费和战斗值，选定一个大小为K的联通块使得总战斗值和总费用比值最大
分析
二分答案，然后判断答案的可行性，剩下的就是一个树上的最优性背包
判断过程：
DP：f[i][j]表示以i节点为根的子树中选取j个点的最优权值
v数组表示战斗力-花费*比值x,g数组临时存放转移时的权值
\[时间复杂度O(N^2 * \log ans)\]常数略大，注意精度
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define eps 1e-6
#define inf 1e8
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=2e3+506;
struct edge{int to,next;}e[maxn<<1];
int last[maxn],n,k,size[maxn],w[maxn],c[maxn],cnt=0;
double f[maxn][maxn],g[maxn],v[maxn];
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
void build(double x){
rep(i,0,n){
v[i]=w[i]-x*c[i];
rep(j,0,n)f[i][j]=-inf;
}
}
void update(int x,int y){
rep(i,0,size[x]+size[y])g[i]=-inf;
rep(i,0,size[x])
rep(j,0,size[y])g[i+j]=max(g[i+j],f[x][i]+f[y][j]);
size[x]+=size[y];
rep(i,0,size[x])f[x][i]=max(f[x][i],g[i]);
}
void dfs(int x){
size[x]=0;f[x][0]=0;
reg(x)dfs(e[i].to),update(x,e[i].to);
dep(i,size[x],0)f[x][i+1]=f[x][i]+v[x];
size[x]++;f[x][0]=0;
}
int main(){
k=read(),n=read();k++;
rep(i,1,n){
c[i]=read(),w[i]=read();int x=read();
insert(x,i);
}
double l=0,r=10000,ans;
while(fabs(l-r)>eps){
double mid=(l+r)/2;
build(mid);dfs(0);
if(f[0][k]>0)ans=mid,l=mid;else r=mid;
}
printf("%.3lf\n",ans);
return 0;
}
