二、分析
这道题其实一眼看过去就是一个树形背包DP，但是这道题唯一特别的就是其中涉及到了分数。当我们求一个分数的最值的时候，我们通常使用的是二分。
1、分数规划
当题目中让我们求：∑ a i ∑ b i \frac{\sum a_i}{\sum b_i}
∑b
i
∑a
i
的最大值的时候，我们应该怎么做呢？
不妨设：
∑ a i ∑ b i = x \frac{\sum a_i}{\sum b_i}=x
∑b
i
∑a
i
=x
那么就有：
∑ a i = x m a x ∗ ∑ b i \sum a_i = x_{max} * \sum b_i
∑a
i
=x
max
∗∑b
i
即：
∑ a i − x m a x ∑ b i = 0 \sum a_i - x_{max}\sum b_i=0
∑a
i
−x
max
∑b
i
=0
我们可以将这几个求和融合一下：
∑ ( a i − x ∗ b i ) = 0 \sum(a_i-x*b_i)=0
∑(a
i
−x∗b
i
)=0
因此，我们可以让括号内的式子是C i C_iC
i
我们会发现一个特点∑ C i \sum C_i∑C
i
是关于x xx的单调函数，因此我们可以使用二分，而二分中的c h e c k checkcheck函数其实就是利用树形DP求出上面求和式的最大值，然后进行判断。
我们这里用到的二分是浮点数二分。
整个过程的时间复杂度是O ( n 2 l o g n ) O(n^2logn)O(n
2
logn)的。（树形背包DP看似是O ( n 3 ) O(n^3)O(n
3
)的，但实际上当我们对其上下界进行优化后，可以到达O ( n 2 ) O(n^2)O(n
2
)）。
2、树形DP
状态表示
f [ u ] [ j ] f[u][j]f[u][j]表示在以u uu为根的树（包括u uu）中选j jj个节点，∑ c i \sum c_i∑c
i
的最大值。
状态转移
f [ u ] [ j ] = m a x ( f [ u ] [ j ] , f [ u ] [ j − q ] + f [ s o n ] [ q ] ) f[u][j]=max\bigg(f[u][j],f[u][j-q]+f[son][q]\bigg)
f[u][j]=max(f[u][j],f[u][j−q]+f[son][q])
初末状态
f [ u ] [ 1 ] f[u][1]f[u][1]表示选一个，所以就是f [ u ] [ 1 ] = c [ u ] f[u][1]=c[u]f[u][1]=c[u]
f [ u ] [ 0 ] f[u][0]f[u][0]表示选0个，所以就是f [ u ] [ 0 ] = 0 f[u][0]=0f[u][0]=0
由于题目中选0 00节点不算进我们方案，但是我们在计算的时候，还是要算入我们的答案的，所以我们代码中选择的实际上是k + 1 k+1k+1个点。最终的状态即：f [ 0 ] [ k + 1 ] f[0][k+1]f[0][k+1]
三、代码
