0%

「九省联考 2018」秘密袭击

「九省联考 2018」秘密袭击

给一棵树,点有点权$w_i$。给定$k$,求所有大小至少为$k$的连通块的第$k$大点权和。模64123

$n\le 1666,w_i\le 1666.$ 时限5s.

一道有意思又有点套路的数数好题。(可惜被暴力草了?

暴力

按照套路,枚举第$k$大点权$x$.令$cnt(x)$表示包含至少$k$个权值不小于$x$的点的连通块数量。

答案即为

然后$cnt(x)$我们可以做树上背包来求。总复杂度$\mathcal O(n^3)$ 。(听说能过

我的做法

按照LOJ 花朵 的套路,我们进行链分治。重儿子的贡献和其余儿子的贡献都可以描述成矩阵(其中每个元素是一个生成函数),然后用NTT+分治 合并这些矩阵即可(这题模数不能NTT,但FFT不会爆精度),将树上背包的复杂度降为$\mathcal O(n\log^ 3n)$. 卡常后(展开矩乘等)能过。

My code

官方做法

考虑那个树上背包的生成函数。

$a_k$表示,点$u$的子树中,选取一个包含$u$的连通块且满足权值超过$i$的点数量恰为$k$的方案数。

合并的时候要卷积复杂度太高,按照套路,我们只带入$n+1$个点值,最后再恢复这个生成函数(具体恢复之后说)

考虑转移,即$F(u,i)=x^{[a_u\ge i]}\cdot \prod_{v\in son(u)} (F(v,i)+1)$

(注意此时$x$已经是个具体的值了)

此外还要再维护$G(u,i)=\sum_{v\in subtree(u)}F(v,i)$ 便于最后算答案,因为最终的连通块可以以任何一个点为根。

暴力做还是$\mathcal O(n^3).$

考虑整体DP的思想,用线段树合并优化这个事情,每个点开一个动态开点线段树,第$i$个叶子维护$F(u,i),G(u,i)$。

我们要支持以下操作:

  1. 初始化,$\forall i,F(u,i)=1$.
  2. dfs所有儿子并合并($F(u,i)\leftarrow ^{\times}(F(v,i)+1);G(u,i)\leftarrow ^{+}G(v,i)$
  3. 乘上$x^{[a_u\ge i]}$,即$\forall i\le a_u,F(u,i)\leftarrow F(u,i)x$
  4. $\forall i,G(u,i)\leftarrow^{+} F(u,i)$
  5. dp式子里面$\prod (F(v,i)+1)$所以可以最后$\forall i,F(u,i)\leftarrow^{+}1$

上面这些操作都可以用矩阵描述(准确的说官方做法是写成一个变换,但本质是一样的),令每个点维护一个动态开点线段树维护这些矩阵就好了,唯一麻烦的是我们要合并儿子:用特种线段树合并来做这个事情,具体说就是:

当前要合并点$a$和$b$.有一个为空直接返回;否则,若有一个点两个儿子都没有,就把他的标记直接乘到另一个点上;否则两边都pushdown(若需要新建节点则新建之)然后递归合并。

分析一下复杂度。根据$\color{black}h\color{red}ehezhou $的指导,考虑如果线段树上每个点都是没有儿子或有恰两个儿子的,那么每次有效合并至少减掉一个点;对于有一个儿子的点,pushdown一次之后变成了有恰两个儿子的点。

对$n+1$个点值都做一次,总复杂度$\mathcal O(n^2\log n)$.最后我们要用点值反推系数。这一步可以用另一种拉格朗日插值:

考虑原本的插值式子:

记$T=\prod _i(x-x_i)$,则$f(x)=\sum y_i\frac{T}{x-x_i}\prod_{i\ne j} \frac{1}{x_i-x_j}$

$T$可以$O(n^2)$预处理那么求一次$\frac{T}{x-x_i}$是$O(n)$,后面$\prod_{i\ne j} \frac{1}{x_i-x_j}$ 就暴力。对$n+1$个$(x_i,y_i)$都做一次,并加到对应的系数上就好。可见代码。

My code

续:由于线段树合并常数惊人,所以甚至可能跑不过暴力。