A. 战略游戏

容易发现完全覆盖的边是连续的。

考虑暴力做法，枚举两个点表示完全覆盖的路径，统计答案是两个点相对于父边的权值相乘。

可以发现这个权值可以表示为一个简单生成函数的形式，去掉一条边的贡献，可以表示为直接除掉一个简单的多项式 $(k*x+1)$ 。

但是不管怎么做复杂度都是 $O(n^2)$ 的。

观察部分分，对于链，可以将很多答案放在一起考虑。

对于菊花图，可以发现很多的权值是一样的。

所以可以发现，可以对每个点的每种儿子的$size$记忆化一个答案。

在不能找到答案的时候暴力计算，这样的话总复杂度为 $O(\sum \limits_{i=1}^{n}deg_i*n^{0.5})=O(n^{1.5})$。

 

B. 小b爱取模

感觉是一道非常神仙的题。

考虑将原数组差分。

区间修改变单点修改，问题转化为将差分数组的每一位都变为 $0$ 。

考虑这样的一个做法。

首先认为每个点都是左端点，得到一个答案数组 $c$ 。

之后不断调整，调整的方向如下

如果 $\sum \limits_{j=1}^{i}c_j-k$ ，那么 $c_i$ 可以不作为左端点，而充当一个右端点。

否则，可以考虑原来的一个右端点，如果原来的右端点不够优秀，可以使当前点充当一个右端点，而将右端点替换为左端点。

这样的操作只会使得一段前缀和增大，总答案减小，所以显然是正确的。

 

C. 小b爱实数

考试时的思路有点弱智。

太局限于01分数规划的思路了。

所以想的是分别二分，当方案数发生变化的时候即找到了答案，然后通过eps判断一下答案在哪即可。

其实推一下式子就可以发现问题是简单的求点对斜率绝对值的最小值。

考虑求斜率最大值，那么只有横坐标相邻的两个点是需要考虑的，因为可以调整。

斜率最小值实际上就是交换横纵坐标后的斜率最大值的倒数，所以按纵坐标排序即可。