一、题目描述：
给你一颗 $n$ 个节点的有根树。节点 $i$ 的价值为 $v_i$，费用为 $w_i$。
你需要选择 $k$ 个节点，使得 $\frac{\sum_{i=1}^nv_i}{\sum_{i=1}^nw_i}$ 最大。
约束：选择一个节点之前，必须先选择它的父亲节点。（根节点除外）
输出 $\frac{\sum_{i=1}^nv_i}{\sum_{i=1}^nw_i}$ 的最大值。答案精确到三位小数。
数据范围 $1\le k\le n\le 2500，1\le v_i,w_i \le 1\times 10^4$。
二、解题思路：
是我以前从未见过的分数规划题目。
分数规划题的形式就是让你求 $\frac{\sum_{i=1}^kv_i}{\sum_{i=1}^kw_i}$ 的最值。
其实写了一道题就不难了，个人觉得比较套路。一般我们二分求解分数规划。过程如下：
$二分枚举答案\ mid\ $
$若\ mid\ 成立，说明存在一组树上的点使得\ \frac{\sum_{i=1}^kv_i}{\sum_{i=1}^kw_i}>=mid\ $
$化一下式子，得到\ \sum_{i=1}^k(v_i-mid\times w_i)>=0\ $
$令每个点\ x\ 的权值\ g(x)=v_x-mid\times w_x\ $
$问题转化为求\ k\ 个最大的\ g(x),是否和大于0\ $
于是就是比较板的树形背包题了，时间复杂度 $O(nk\times log_2^{1e8})$
三、完整代码：
1 #include<iostream> 2 #include<iomanip> 3 #include<algorithm> 4 #define N 3010 5 #define ll long long 6 #define rep(i,l,r) for(int i=l;i<=r;i++) 7 #define per(i,r,l) for(int i=r;i>=l;i--) 8 #define tep(i,u) for(int i=head[u];i!=-1;i=e[i].nxt) 9 using namespace std; 10 int n,m,s[N]; 11 double g[N],v[N],w[N],f[N][N]; 12 struct EDGE{ 13 int v,nxt; 14 }e[N*2]; 15 int head[N],cnt; 16 void add(int u,int v){ 17 e[++cnt].v=v; 18 e[cnt].nxt=head[u]; 19 head[u]=cnt; 20 } 21 void Max(double &a,double b){a=max(a,b);} 22 void solve(int u,int ff){ 23 tep(i,u){ 24 if(e[i].v==ff) continue; 25 int to=e[i].v;solve(to,u); 26 per(j,min(s[u]+s[to],m),2) 27 rep(k,max(1,j-s[u]),min(s[to],j-1)) 28 Max(f[u][j],f[u][j-k]+f[to][k]); 29 s[u]+=s[to]; 30 } 31 } 32 bool check(double val){ 33 rep(i,1,n) 34 g[i]=v[i]-val*w[i]; 35 rep(i,0,n) 36 rep(j,0,m) 37 f[i][j]=-1e9; 38 rep(i,0,n) 39 s[i]=1,f[i][1]=g[i]; 40 solve(0,0); 41 return f[0][m]>=0; 42 } 43 int main(){ 44 ios::sync_with_stdio(false); 45 cin.tie(0);cout.tie(0); 46 cin>>m>>n;m++; 47 rep(i,0,n) 48 head[i]=-1; 49 rep(i,1,n){ 50 cin>>w[i]>>v[i]; 51 int ff;cin>>ff,add(ff,i); 52 } 53 double l=0,r=1e4,eps=0.0003; 54 while(l+eps<=r){ 55 double mid=(l+r)/2; 56 if(check(mid)) l=mid+eps; 57 else r=mid-eps; 58 } 59 cout<<fixed<<setprecision(3)<<l<<'\n'; 60 return 0; 61 }
四、写题心得：
收获经验如下：
$1、新知识 \to 分数规划。=> Exp++!$
$2、树形背包竟然是\ O(n^2)\ 的，震惊 ! => Exp++!$