P4322

一、题目描述： 给你一颗 $n$ 个节点的有根树。节点 $i$ 的价值为 $v_i$，费用为 $w_i$。 你需要选择 $k$ 个节点，使得 $\frac{\sum_{i=1}^nv_i}{\sum_{i=1}^nw_i}$ 最大。 约束：选择一个节点之前，必须先选择它的父亲节点。（根节点除外） 输 ......

[P4322 [JSOI2016]最佳团体](https://www.luogu.com.cn/problem/P4322) 分数规划+树形背包。 可以根据推荐关系建出一颗树，然后如果选了一点，则该点到根上的所有点都必须选。 二分 $mid$，定义每个结点的权值，然后判断选 $k+1$ 个节点的最大 ......