首先，你要知道这道题是一棵树！
然后，就是从树上选择K个点，让他们的权值和最大，其中如果选择了一个点，那么它的父亲一定要选。
有依赖的背包问题。
设\(dp[i][j]\)表示在以i为根的子树中，选择j个点的最大权值。
但是直接在树上做应该是\(O(n^2k)\)的，所以我们考虑优化——
就是我们考虑在树上将背包合并，这样子每个子树都只会被合并一次，这样时间复杂度就降为了\(O(nk)\)
然后就能过了。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define MAXN 3010#define eps 1e-6using namespace std;int n,m,t,tot;int head[MAXN],siz[MAXN],fa[MAXN];double dp[MAXN][MAXN],now[MAXN],tmp[MAXN],w[MAXN],v[MAXN];struct Edge{int nxt,to;}edge[MAXN<<1];inline void add(int from,int to){edge[++t].nxt=head[from],edge[t].to=to,head[from]=t;}inline void merge(int x,int y){ for(int i=0;i<=m+1;i++) tmp[i]=-1e9; for(int i=1;i<=siz[x];i++) for(int j=1;j<=siz[y];j++) tmp[i+j]=max(tmp[i+j],dp[x][i]+dp[y][j]); for(int i=0;i<=m+1;i++) dp[x][i]=max(dp[x][i],tmp[i]);}inline void solve(int x){ dp[x][1]=now[x]; siz[x]=1; for(int i=head[x];i;i=edge[i].nxt) { int v=edge[i].to; solve(v); merge(x,v); siz[x]+=siz[v]; }}inline bool check(double x){ for(int i=0;i<=n;i++) for(int j=0;j<=m+1;j++) dp[i][j]=-1e9; memset(siz,0,sizeof(siz)); for(int i=1;i<=n;i++) now[i]=v[i]-w[i]*x; solve(0); if(dp[0][m+1]>=0) return true; else return false;}int main(){ #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif scanf("%d%d",&m,&n); double l=1e9,r=-1e9; for(int i=1;i<=n;i++) { scanf("%lf%lf%d",&w[i],&v[i],&fa[i]); add(fa[i],i); l=min(l,v[i]/w[i]); r=max(r,v[i]/w[i]); } while(l+eps<r) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.3lf\n",l); return 0;}
