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,P i≤10^4,0≤ Ri < i。
Output
輸出一行一個實數，表示最佳比值。答案保留三位小數。
Sample Input
1 2
1000 1 0
1 1000 1
Sample Output
0.001
題解：
01分數規劃的變種。因為資料之間形成了樹形的結構，是以在樹上做背包，利用01分數規劃的思想，二分比值（答案），在樹上做最優背包，如果戰鬥力-花費*比值>0，說明該答案可行，否則不可行。令f[i][j]表示i為根的子樹中選取j個點時的最大權值,用背包暴力轉移,複雜度O(log（ans）*N²)。二分注意一下精度。
代碼如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#define ll long long
#define inf 1e20
#define eps 1e-5
#define N 2505
using namespace std;
int m,n;
double s[N],p[N],d[N],f[N][N];
int e[N<<1],nex[N<<1],fa[N],hd[N],tot,cnt,dfn[N],las[N];
void add(int u,int v) {e[++tot]=v,nex[tot]=hd[u],hd[u]=tot;}
void dfs(int u)
{
dfn[u]=cnt++;
for(int i=hd[u];i;i=nex[i]) dfs(e[i]);
las[dfn[u]]=cnt;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%d",&s[i],&p[i],&fa[i]);
add(fa[i],i);
}
dfs(0);
double l=0,r=10000.0;
while(l+eps<=r)
{
double mid=(l+r)/2.0;
for(int i=1;i<=n;i++) d[dfn[i]]=p[i]-mid*s[i];
for(int i=1;i<=n+1;i++)
for(int j=0;j<=m+1;j++) f[i][j]=-inf;
for(int i=0;i<=n;i++)
for(int j=0;j<=min(i,m+1);j++)
{
if(f[i][j]+d[i]>f[i+1][j+1]) f[i+1][j+1]=f[i][j]+d[i];
if(f[i][j]>f[las[i]][j]) f[las[i]][j]=f[i][j];
}
if(f[n+1][m+1]>=eps) l=mid;
else r=mid;
}
printf("%.3lf\n",l);
return 0;
}