题解 P4365 【[九省联考2018]秘密袭击coat】

这篇题解写的是**官方正解**。 建议直接去我博客里看，因为这里插不了多行公式，[链接](https://zhang-rq.github.io/2018/05/04/%E4%B9%9D%E7%9C%81%E8%81%94%E8%80%832018-%E7%A7%98%E5%AF%86%E8%A2%AD%E5%87%BBCoaT/) 正解需要以下知识 - 整体DP - 多项式初步 - 拉格朗日插值法 ~~(可以在[这里](https://Zhang-RQ.github.io/2018/05/04/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E6%8F%92%E5%80%BC%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/)学)~~ - 生成函数 - 线段树合并 题目大意： ​ 给一颗有$N$个点的树，点权在$1 \sim W$之间，求树的每一个联通块的第$K$大点权之和。 看到这个题时，我的心里是懵逼的。 我们首先开始考虑转化题目。 $Ans = \sum\limits_{S \in T} k_{th} \ \ of \ \ S \ \ \ \ (1)$ $Ans = \sum\limits_{i=1}^{W} i \times \sum_{S \in T} [k_{th}\ of \ S==i] \ \ \ \ (2)$ $Ans =\sum\limits_{i=1}^{W} \sum_{S \in T} {[k_{th} \ of \ S \geqslant i]} \ \ \ \ (3)$ $Ans =\sum\limits_{i=1}^{W} \sum_{S \in T} {[cnt[i] \geqslant k]} \ \ \ \ (4)$ $(1)$到$(2)$的过程是枚举每个权值的贡献。 $(2)$到$(3)$的过程比较难理解，我们直接考虑从每个$i$在公式$(2)$中会被算多少次，显然是$i$次。 那在公式$(3)$中也是会被算$i$次。 $(3)$到$(4)$的过程就比较显然了，这里不再赘述。 那么到现在，问题就变得比较显然了： 枚举权值$v$,求树上权值$v$出现次数超过$k$的联通块个数。 我们设计一个DP。 $f[i][j][k]$表示以$i$为根的子树中，权值大于等于$j$的权值出现为$k$次的方案数。 转移显然 $f[i][j][k] = \prod\limits_{v \in son[i]} f[v][j][k'] \ \ \ \ (d[i] < j,\sum k'=k) $ $f[i][j][k] = \prod\limits_{v \in son[i]} f[v][j][k'] \ \ \ \ (d[i] \geqslant j,\sum k'=k-1)$ 最后答案就是$\sum\limits_{k'=1}^{k}\sum\limits_{j=1}^{W}\sum\limits_{i=1}^{N} f[i][j][k']$ 复杂度$\mathcal{O}(N^2*k)$，据说有人大力过了。 我们考虑优化这个转移，不难发现，这个DP其实是背包的一种，而转移就是背包的合并。 那我们不妨直接考虑生成函数。 设$F[i][j]$表示以$i$为根的子树中，权值大于等于$j$的权值的生成函数。 则$F[i][j]=\sum\limits_{k=0}^{n} f[i][j][k] \times x^k$，这是一个$N$次多项式。 但是最后我们要求的是整棵树的所有$F[i][j]$之和，所以我们不妨再设一个$G[i][j]$。 $G[i][j]=\sum\limits_{x \in subtree(i)}F[x][j]$ $F[i][j]$在转移时是多项式卷积，还是很慢，$G[i][j]$在转移时只要维护一下就行了。 所以我们考虑将它转换为$N+1$个点值，这样的话转移时就是普通乘法了。 我们就令$x=1 \sim N+1$，然后将所有$G[i][j]$在$x$时的值都求出来，最后进行拉格朗日插值法将原始的多项式差出来就行了，可具体怎么实现呢？ 我们首先在最外层枚举$x \in [1,N+1]$，然后每次进行一次$DFS$，但具体如何进行转移呢？ 我们不难发现，$F[i][j] \leftarrow F[son[i]][j]$转移过程中其实就是$[j]$的对应位置相乘。 所以我们可以使用整体$DP$的思想在每个点上都维护一颗线段树，然后在转移时进行线段树合并就可以了。 正解差不多就是这个意思。 具体合并方法如下： 初始化： $ F[i][j] = x \ \ \ \ (d[i] \geqslant j) $ $F[i][j] = 1 \ \ \ \ (d[i] < j) $ 转移时： $F[i][j] \times =(F[son[i]][j]+1) , G[i][j]+=G[son[i]][j]$ 最后，$G[i][j]+=F[i][j]$。 我们可以将$F[son[i]][j]+1$的操作放在$DFS$ son[i]后进行。 可是你说了这么多，线段树到底应该怎么写？ 我们设变换$(a,b,c,d)$可以使$(f,g)$变换为$(a \times f+b,c \times f+d+g)$ 然后每个线段树维护一个变换即可。 变换结合的话手推一下即可。 注意：变换在普遍情况下没有交换律，只有结合律。 剩下的实现方法详见代码。 注意以下坑点： - 模数是64123，做乘法时要用unsigned int。 - unsigned int 取模时模数必须是unsigned类型。 - 初始化变换时应该是$(1,0,0,0)$ [代码](https://zhang-rq.github.io/2018/05/04/%E4%B9%9D%E7%9C%81%E8%81%94%E8%80%832018-%E7%A7%98%E5%AF%86%E8%A2%AD%E5%87%BBCoaT/)