题解 P5291 【[十二省联考2019]希望】
smarthehe
·
·
题解
UPD on 2021.1.8：加了一张图。
给定一棵 n 个点的树，问选出 k 个非空连通块使得其交集中存在一个点距离其并集中任一个点均 \leq L 的方案数。对 998244353 取模。
n\leq 10^6$，$0 \leq L \leq n$，$1\leq k \leq 10
V=E+1 容斥
令题意里交集中的那个点是关键点。一个方案可能有多个关键点，然而其必定构成连通块。对于每个点统计其为关键点的方案，然后对于每条边统计其两端均为关键点的方案，相减。树上连通块满足顶点数为边数+1。对于每个方案都会在其关键点连通块中的每个点处统计一次，在每个边处减去一次，因此会统计恰好一次。
树形 DP + 换根 DP
令 f_{i,j} 为只在以 i 为根的子树内选点，每个点距离 i 不超过 j，所能统计出来的连通块（可能为空，如果非空则必须包括 i）方案数。
令 g_{i,j} 为只在以 i 为根的子树外与 i 的并集选点，每个点距离 i 不超过 j，所能统计出来的连通块（必须包括 i）方案数。
转移，令 k 为 i 的父亲。
f_{i,j}=\prod_{x \in son_i} f_{x,j-1} +1
g_{i,j}=\left(\prod_{x \in son_k,x \neq i} f_{x,j-2} \right) \times g_{k,j-1} +1
一个点 i 的答案是
((f_{i,L}-1) \times g_{i,L})^k
一条边的答案在儿子点 i 处统计。
((f_{i,L-1} -1) \times (g_{i,L}-1))^k
复杂度 O(nL)。
长链剖分 + 常数时间数据结构
分为自底而上的长链剖分与（优化 f）与自顶而下的长链剖分（优化 g）。
优化 f
具体地，假设我们遍历到节点 $x$。如果节点 $x$ 向下深度为 $d_x$，那我们会在最终合并后的长链上存储 $f_{x,0}$ 到 $f_{x,d_x}$。
在把节点 $y$ 合并上来的时候，$f_{y,0} \rightarrow f_{x,1}$，$f_{y,1} \rightarrow f_{x,2}$，以此类推。
但是这样有一个问题：其他子树深度小于长子树深度，但考虑到状态的定义它们无可避免地会对更深的状态作出贡献。
比如 $y$ 向下深度为 $d_y$。那么对于 $f_{x,i}$（$i > d_y+1$），其仍会收到来自 $f_{y,d_y}$ 的贡献，不然答案不对。
如果暴力提供贡献，复杂度又不对。（长链剖分的线性复杂度分析源于一条长链上的点只会被合并一次，但暴力则会遍历多次同一条长链）
当然可以线段树之类维护，但如果这样就多了个 $\log$，明显又难写又不优。
注意到这只是一个后缀乘，并且如果我们能转化成除掉该后缀以后的前缀乘复杂度就对了。（这样把复杂度转化到了合并的长链上，仍能沿用如上分析）
那么我们只需要全局乘，然后把前面那部分乘逆元。维护一个 $mul$，为全局乘的 tag。
但是合并完还要全部 $+1$，没法处理。我们再维护一个 $add$，为全局加的 tag。不妨利用线段树下传思想强制令 $mul$ 比 $add$ 先作用。
在更新数据的时候也有问题。由于 $add$ 和 $mul$ 的存在，我们不知道一个数更新以后要成为什么。
> 具体情形：
>
> 数组里存的是 $x$，$add=a$，$mul=m$。
>
> 现在我们在合并另一条长链，这个位置要乘上 $y$。
>
> 这个位置的实际值是 $mx+a$，更新后的实际值应该是 $mxy+ay$。
>
> 为了得到数组中的值，减掉 $a$ 再除去 $m$，这个东西是 $xy + \dfrac{ay-a}{m}$，看上去分母约不掉，没法处理了。
维护 $imul$ 表示 $mul$ 的逆元，然后就可以处理了。
最后还有一个问题：如果后缀乘的那个东西 $f_{y,d_y}\equiv0 \pmod p$ 怎么办？此时没有逆元。
容易看到可以看作后缀赋值。如果暴力合并部分没有到达此处，这个后缀的值将一直相同。我们可以用 tag 来维护后缀同值连续段长度与这个值。
另定义 $zlim$ 为同值边界，代表从该位置以后 $f$ 值全部相同。 $zval$ 为当前的这个同值（这个值当然也受 $add$ 和 $mul$ 的影响）。
维护方法是：
- 如果暴力合并波及到了 $zlim$ 以后的部分，就在合并时不断将 $zlim$ 后移，根据 $zval,add,mul$ 来计算真实值参与合并；
- 如果当前的这个 $f_{y,d_y}$ 是 $0$，那么更新 $zlim$，并利用 $add$ 和 $imul$ 求出一个能使得变换后为 $0$ 的值赋给 $zval$。
于是我们就利用 $add,mul,imul,zval,zlim$ 五个 tag 所构建的 $O(1)$ 数据结构完成了对 $f$ 的更新。总复杂度保持 $O(n)$。
#### 优化 $g$ 前半部分
$g$ 是一个换根 style 定义的 dp，它的转移是从父亲转向儿子的。
然而我们依旧可以尝试对其长链剖分优化。
注意到我们在遍历到每个点的时候，需要存储的状态实际上是有限的。我们对于每个节点，实际上只需要知道 $g_{x,L}$ 的值就够了，其他的存储都是为了方便更新。
观察转移式子，$g_{x,i}$ 的转移对父亲的利用仅限于 $g_{k,i-1}$，也就是只会丢失一个位置的信息。所以对于每个点 $x$ 我们实际上只需要 $g_{x,L-d_x}$ 到 $g_{x,L}$，就能让子树中所有点的有用信息都得以统计。
这个信息数量不就是长链长度嘛。
假设我们遍历到节点 $x$。如果节点 $x$ 向下深度为 $d_x$，那我们在最终合并后的长链上自顶而下存储 $g_{x,L}$ 到 $g_{x,L-d_x}$。
自底而上的长链剖分采用合并方法，自顶而下的长链剖分采用分裂方法。我们让长儿子继承父亲的信息并更新，其他长链的信息根据当前信息暴力全部处理出来。
设 $l$ 为 $x$ 的长儿子。那么 $g_{x,i}$ 会在继承后变成 $g_{l,i+1}$。把转移式列出来。
$$
g_{i,j}=\left(\prod_{x \in son_k,x \neq i} f_{x,j-2} \right) \times g_{k,j-1} +1
$$
考虑转移式里面的那个大 prod。这个大 prod 似乎可以通过 $f_{k,j-1}$ 做除法来转移？但是一旦 $f_{x,j-2} \equiv 0 \pmod p$ 就又完蛋了。
另一个思路：除了长儿子以外的其他儿子都是长链链顶，它们的 $f$ 信息保存完好，没有在合并中丢失。定下一个固定的儿子枚举顺序，这样我们在算到当前儿子的时候可以顺带处理出前缀的这个 prod 数组（需要一个类似的处理 $f$ 时的数据结构，但只需要维护 $mul$ 和 $zlim$），就只需要解决后缀的 prod 数组了。
似乎我们在之前处理 $f$ 的时候，我们枚举儿子的时候也可以顺便得出一部分儿子的这个 $f$ 乘积信息？能不能尝试存下来？
我们令枚举儿子的时候，在处理 $f$ 时按深度从深到浅枚举，处理 $g$ 时反向。这个排序过程可以利用桶排，把所有点的所有儿子塞进去一并排序，这样还是线性的。
每次合并长链的时候，只有那两个 tag 和等同于长链长度的信息会被更改。于是可以强行套上可持久化数组，每个版本基于上一个版本进行等同于合并上长链的长度次数的更改，并对于每个版本再维护两个 tag，这样根据长链剖分的复杂度分析，时空是 $O(n\log n)$ 的。
这里的一个细节是初始版本的存储问题。由于时空原因我们肯定不能把整条长链的信息拉出来做初始版本。注意到只需要 $f_{i,L-mxd_k-1}$ 到 $f_{i,L-1}$，其中 $mxd_k$ 为以 $k$ 的儿子为根的子树中除去长子树外的最大深度。这样时空就对了。实际上对于每个版本也不需要求所有更改，只需要存储 $f_{i,L-d_x-1}$ 到 $f_{i,L-1}$ 这些值就好了。
对于每个非长儿子，我们枚举所有应计算出的信息，用存好的 prod 数组和可持久化数组求这个系数。
对于长儿子，我们在枚举其他儿子的时候顺带在上面乘好。此处也有后缀乘、整体加和查询的需求。利用那五个 tag 构建一个同样的 $O(1)$ 数据结构来维护。
但是由于带了可持久化的问题，不仅有 $\log$，常数还大，完全不优。
### 优化 $g$ 后半部分——回退化数据结构
发现对版本的询问是有规律的：我们只会倒序枚举版本，从最新枚举到最旧。
这样我们可以强行将每次需要的部分直接打包存储成为一个版本，然后把所有版本压成栈，每查询一次便弹出一个版本。复杂度还是对的。
总复杂度保持 $O(n)$……？
### 线性求逆元
等等，我们忘掉了什么。
在处理 $f$ 和 $g$ 的时候，好像用到了逆元。那不就得快速幂求吗？我们算法的常数已经很大，$O(n \log p)$ 显得更加不可接受。
但是注意到，对于每个 $x$，我们只需要 $f_{x,d_x}$ 的逆元。而这个东西就是没有 $L$ 限制的子树连通块个数，有一个非常简易的 $O(n)$ dp 能求出所有点的 $f_{x,d_x}$。这样就可以把所有 $f_{x,d_x}$ 拉出来线性求逆元了。
具体地，将其排成数列，排除 0 项，然后处理前缀积，后缀积，并求出全部之积的逆元。每个数的逆元只需要用前缀积、后缀积与全部之积的逆元相乘可得。复杂度 $O(n)$。
### 收束 & 遗憾
然而这个答案式的 $k$ 次方实在是无法消掉……不过这部分常数很小。最终的复杂度是 $O(n\log k)$。
总结一下步骤：
1. 利用 $V=E+1$ 容斥拆分问题。
2. 预处理所有 $f_{x,d_x}$，线性求逆元；预排序所有点的所有儿子。
3. 扫一遍求 $f$，深度从深到浅枚举所有儿子，并使用五 tag $O(1)$ 数据结构配合长链剖分优化。过程中处理出后缀 prod 数组中每个对应部分，将其压栈。为了防止之后信息被破坏，将需要用于统计答案的 $f_{i,L}$ 与 $f_{i,L-1}$ 存好。
4. 扫一遍求 $g$，深度从浅到深枚举所有儿子。利用 $g_{i,L}$ 和提前存好的 $f$ 处理出该点的答案（以及到父亲的那条边的答案）。使用两 tag $O(1)$ 数据结构维护前缀 prod 数组，五 tag $O(1)$ 数据结构配合长链剖分优化。