CF1930G 题解

sunkuangzheng · 2024-02-19 17:51:22 · 题解

题目链接。

• 给定 n 个点的树，问所有 dfs 序只保留前缀 \max 后有多少不同的数组，模 998244353。“只保留前缀 \max” 指去除所有非前缀 \max 元素，例如 [2,5,3,6,1] \to [2,5,6]。

考虑 DP。设 f_u 表示路径以 u 结尾且 u 是前缀 \max 的方案数，但是转移成了难题。我们来观察一些性质。以下设 a 是只保留前缀 \max 的 dfs 序。

• 性质一：a_{i+1} 是 a_i \to a_{i+1} 路径上的最大值，且 a_i 是路径上的次大值。

分两种情况：如果 a_i 是 a_{i+1} 的祖先，那么路径上如果存在大于 a_{i} 的元素 x，元素 x 一定在 a_i 和 a_{i+1} 之间，导致 a_i 和 a_{i+1} 在 a 数组中下标不相邻，矛盾。

如果 a_i 不是 a_{i+1} 的祖先，令 d = \operatorname{lca}(a_i,a_{i+1})，显然 a_i \to d 的路径上不存在大于 a_i 的元素。d \to a_{i+1} 的路径上若存在 >a_{i} 的元素则同理可发现矛盾。

• 性质二：若 a_i 不是 a_{i+1} 的祖先，令 d = \operatorname{lca}(u,v)，k 为 a_i 的 dep_{a_i}-dep_d-1 级祖先，则 a_i 是 k 子树里的 \max。

如果 k 子树里存在大于 a_i 的元素 x，如果它的 dfs 序在 a_i 前面则 a_i 不是前缀 \max，如果在 a_i 后面则 x 会在 a_i 和 a_{i+1} 之间。

我们可以开始 DP 了。如果 u 不是 1 \to u 的 \max，则 f_u = 0。否则，令 x 为 1\to fa_u 的 \max，则 u 可以从 x 直接下来，也可以从 1 \to fa_u 路径上任意一个点的任意一个直接儿子 v 的子树 \max 转移过来，当然要求这个值小于 u 大于 x 防止算重。我们用树状数组维护儿子 v 的子树 \max 即可，在 dfs 的过程中进行转移。时间复杂度 \mathcal O(n \log n)。注意初始化 f_1 =1，参考代码。

当然我们还可以让 DP 式子更加简洁：注意到 x 的转移点一定是 1 \to fa_x 路径上某一个点的儿子 v 子树 \max，或是 1 \to fa_x 的路径 \max。我们发现这个 DP 等价于 u 从 1 \to fa_u 的任意一点的直接儿子 v 的子树 \max（仅要求小于 u）转移，或者直接从根走下来，会有 1 的贡献。也即 f_u = 1+\sum \limits_{v} f_v。这样实现起来更加简洁。参考代码。