P5558

· · 题解

P5558题解

简要题意：多次查询树上路径最长非降子序列长度。这里给出的是 DDP 做法。

先考虑在序列上的做法，一般地，我们可以考虑设 f_i 表示到 i 为结尾的最长非降子序列长度。

那么我们有 f_i = \max_{j = 1}^{j < i} (f_j+1) [leaf_j \leq leaf_i] 。

这个式子可以通过权值线段树或者树状数组优化复杂度，在此不再赘述。

假如用矩阵维护这个过程怎么做，这要求我们知道前 i 个节点的信息，此时我们难以用矩阵维护。

观察到 1 \leq leaf \leq 5 ，这启示我们可以通过维护与值域有关的信息来进行转移。

那么让我们重新设计状态,设 f_{i,v} 表示到 i 为止末尾枫叶数量为 v 的最长非降子序列。

设 i 号点拥有的枫叶数量为 leaf_i 。

对于 leaf_i \ne v 时，有 f_{i,v} = f_{i-1,v}。

对于 leaf_i = v 时，有 f_{i,v} = \max_{w = 1}^{w \leq v} f_{i-1,w}+ 1 。

如此，我们只需要知道上一个位置的五个信息，这时再通过矩阵乘法（广义）去维护便变得简单了。

考虑定义广义矩阵乘法 C_{i,j} = \max_{k = 1}^{k \leq n} (A_{i,k} + B_{k,j}) ，手玩之后发现这种运算是具有结合律的。

那么我们可以利用其结合律处理出路径上的 “前后缀积”,配合我们树上问题的利器-树链剖分来解决。

考虑如何用矩阵维护我们的信息。

对于一个节点，我们维护他每个值对应的 dp 值 \begin{bmatrix}f_{i,1},f_{i,2},f_{i,3},f_{i,4},f_{i,5}\end{bmatrix} 考虑怎么把上面的转移写成矩阵形式。

手玩一下，在不考虑 leaf_i 时，可以得到一般的转移矩阵 E = \begin{bmatrix} 0&\ -\infty& \ -\infty& \ -\infty& \ -\infty&\\ -\infty&\ 0& \ -\infty& \ -\infty& -\infty& \\ -\infty& \ -\infty& \ 0& \ -\infty& \ -\infty& \\ -\infty& \ -\infty& \ -\infty& \ 0& - \infty& \\ -\infty& \ -\infty& -\infty& \ -\infty& \ 0&\end{bmatrix}

特别地，对于每个 leaf_i 我们只需要把当前矩阵第 leaf_i 列的前 leaf_i 行的元素改为 1 即可。

解释一下为什么需要前后缀积，因为我们的矩阵乘法是不满足交换律的，那么我们便要把从 S \rightarrow T 的过程看作一条有向路径（可以类比成向量）而非一般的信息合并。

理论而言是可以直接维护每条链跳到链首的前后缀积的，但是由于笔者代码水平有限，这里采用线段树维护。

注意矩阵初始化，不要写成全部为 0 的形式，这样会使整个矩阵的信息变得混乱，注意树链上的元素对应线段树的元素的方向，不要写反了，跳链的时候可以画个图理解一下。

code

另附一个数据生成器。data