自动搬运

查看原文

来自洛谷，原作者为

	Zhang_RQ In solitude, where we are least alone.

搬运于2025-08-24 21:59:24，当前版本为作者最后更新于2018-05-05 09:50:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这篇题解写的是官方正解。

建议直接去我博客里看，因为这里插不了多行公式，链接

正解需要以下知识

• 整体DP
• 多项式初步
• 拉格朗日插值法 (可以在这里学)
• 生成函数
• 线段树合并

题目大意：

​ 给一颗有$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)$

代码