题意：给定一棵大小为N的点权树(si,pi)，现在让你选敲好K个点，需要满足如果如果u被选了，那么fa[u]一定被选，现在要求他们的平均值(pi之和/si之和)最大。
思路：均值最大，显然需要01分数规划，但是后面怎么高效的做背包，我是不会的，我只会暴力的背包，O(N*K*K)。 还好队友会，叫“树上依赖背包”，即要问树转化为DFS序，按照倒序来DP，复杂度O(N*K)。dp[i][j]=max(dp[i+1][j-v[x]]+w[x],dp[i+sz[x]][j])，分别对应x选或者不选(其中x是DFS为i的点)。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const double inf=1e20;
double dp[maxn][maxn],s[maxn],p[maxn],val[maxn];
int r[maxn],Laxt[maxn],Next[maxn],To[maxn];
int pos[maxn],tot,cnt,N,K,sz[maxn];
void add(int u,int v)
{
Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;
}
void dfs(int u)
{
sz[u]=; tot++; pos[tot]=u;
for(int i=Laxt[u];i;i=Next[i]){
dfs(To[i]); sz[u]+=sz[To[i]];
}
}
bool check(double Mid)
{
rep(i,,N) val[i]=p[i]-s[i]*Mid;
rep(i,,tot+) rep(j,,K) dp[i][j]=-inf;
rep(i,,tot+) dp[i][]=;
for(int i=tot;i>=;i--){
int x=pos[i];
for(int j=;j<=K;j++){
dp[i][j]=max(dp[i+][j-]+val[x],dp[i+sz[x]][j]);
}
}
return dp[][K]>=;
}
int main()
{
scanf("%d%d",&K,&N); K++;
rep(i,,N){
scanf("%lf%lf%d",&s[i],&p[i],&r[i]);
add(r[i],i);
}
dfs();
double L=,R=,Mid,ans=; int T=;
while(T--){
Mid=(L+R)/;
if(check(Mid)) ans=max(Mid,ans),L=Mid;
else R=Mid;
}
printf("%.3lf\n",ans);
return ;
}