分数规划
前言：教练要求过《算法竞赛》的东西，然后翻了一翻选了一个看起来比较好写的开始。
问题：给出一组\(a_i\) 和 \(b_i\),求一组\(w_i\)，使
\[\frac{\sum a_i \times w_i}{\sum b_i \times w_i}
\]
最小或最大。
考虑进行二分答案，记此时二分到的答案为\(mid\),则有：
\[\frac{\sum a_i \times w_i}{\sum b_i \times w_i} >mid
\]
\[\sum a_i \times w_i - \sum b_i \times w_i \times mid >0
\]
\[\sum w_i \times (a_i -b_i \times mid)>0
\]
则二分check只需求不等式左边的最大值即可。
可以按照刚才的思路去做。
\[\sum w_i \times (a_i -b_i \times mid)>0
\]
这个时候可以考虑01背包，将\(b_i\)当作重量，将\(a_i-b_i \times mid\)作为价值，直接做就行。
此时\(dp_{n,W}\)即为最大值。
这道题还是挺板子的，和之前唯一不同的是这道题是在树上求解的。将\(a_i-mid \times b_i\) 作为权值，每次check时跑最小生成树即可。
其实还是换汤不换药，只要推一推柿子就可以发现可以把\(a_i-mid\)作为边权做就行。然后因为要求得是最小值，所以每次判是否负环就行。
不过似乎有一个\(O(nm)\)的神仙做法 link
不过刚才那个做法就已经足够能通过本题了。