省选模拟28 A. B. C.
考虑一个暴力的做法，枚举树上的每条链，那么贡献只和链两端有关。
对于一个端点，他的贡献可以通过简单dp求出来。通过多项式可以将这个dp的过程优化到$nlog^2$。
考虑上面那个东西的瓶颈在于枚举点对，那么可以将点对分类。
先处理出以某个点为根时，每个点的方案数。那么点对有两类：祖先关系和非祖先关系。
对于非祖先关系，可以简单dp求出来。
对于祖先关系，发现祖先的贡献最多有根号种，暴力处理出来算就行了。
B.
首先将原序列差分，那么一次修改对应一个端点+1，一个端点-1。
考虑先求出来一个初始的答案数组，不管操作次数，只要求合法，那么不难得到。
那么一个合法的答案数组的要求是任意位置前缀和不小于0。
考虑贪心，首先按照差分后的数组的排序，如果大小相同按照位置从后向前，每次贪心的考虑当前位置能否-k。
由于保证了每次修改的影响最小，所以这样是正确的。
C.
把表示一段区间的权值写出来，通分一下，那么可以发现是斜率的形式(我没发现)。
于是要求两点之间斜率绝对值的最小值，不难发现只有可能出现在相邻的y。
于是排完序直接搞就行了。