【题解】2019ZJOI浙江省选day1

考虑对于每个 求出有多少个 ，则可以通过差分得到答案。

先考虑给定S,R如何判断w(S)是否 。考虑根节点的权值如果可以变大，则一定可以变成W+1，如果可以变小，则一定可以变成W-1。因此树形dp，用 分别表示考虑结点i的子树，i的权值能否变成W+1,W-1。时间复杂度 。

再来考虑给定R，如何求出有多少个 。 表示考虑i的子树，有多少个选择叶节点的方案使得 (可以看作是dp套dp)。时间复杂度 。

回到原问题，考虑从小到大枚举R，则每次只有至多两个叶节点的dp信息可能发生变化，因此可以动态dp维护。这样需要维护4*4的矩阵的乘积，不仅有4^3的常数大概率会导致TLE，而且实现起来也很麻烦。

请教@lyx-cjz(比赛时唯一一个ac,orz)后知道了一个更优越的做法。

还是先考虑给定S,R如何判断w(S)是否 。如果S包含W，则一定可以(当然 显然无论如何都不可以)；否则，考虑如果想让根节点的权值变大，原来就>W的结点显然不用变，原来<W的结点能变成W+1就变成W+1；类似的，如果想让根节点的权值变小，原来就<W的结点显然不用变，原来>W的结点能变成W-1就变成W-1。因此 等价于 或 。因此只需要分别做一遍dp即可，具体的dp和上面是类似的。

再来考虑给定R，如何求出有多少个 。只需要用总方案数减去>R的，而这只需对x>W,x<W的集合分别求出>R的方案数，然后相乘即可。以x>W为例，只需 表示 的权值<W的方案数。

这样就可以轻松的使用动态dp优化了。

关于具体实现，首先用 表示 的权值<W的概率，而不是方案数，但这样转移需要分深度奇偶讨论，因此令 ，就可以去掉讨论，得到一个非常简单的转移式： 。