自动搬运

查看原文

来自洛谷，原作者为

	_mcx say goodbye

搬运于2025-08-24 22:11:59，当前版本为作者最后更新于2023-10-14 12:44:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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