P9480 [NOI2023] 深搜

· · 题解

P9480 [NOI2023] 深搜

超级酷的题目！

思路参考了 Rainbow_qwq 的题解，对他的题解进行一些补充。题解最后给出的代码有：n\leq 300 的性质 B，n\leq 300，未卡常正解和卡常后的正解。

首先，T 可以作为 s-DFS 树的充要条件是所有非树边均为返祖边，因为 DFS 树的非树边为返祖边，且如果满足条件则对 T 进行 DFS 就是符合条件的 DFS 顺序。

称非树边 e 覆盖 点 s 当且仅当 e 在以 s 为根的 T 上是横叉边（非返祖边）。易知非树边 e = (u, v) 不覆盖 点 s 当且仅当 s 在以 v 为根时 u 的子树内（称为 u 侧），或以 u 为根时 v 的子树内（称为 v 侧）。

对于性质 B，有两种思路：

顺着前一种思路不容易解决原问题，因此考虑第二种思路。

非树边的形态

定点 1 为根。

建出 S 的虚树 T_S。注意要和我们所理解的虚树做区分：当且仅当 x\in S 或有至少三棵子树（包括向上的子树）含属于 S 的点时，x 才属于虚树。它们的唯一区别在于，当 S 所有点的 LCA d 只有两棵子树含属于 S 的点时，d 不属于 T_S，但 d 属于我们通常所理解的虚树。

考虑非树边 e = (u, v) 不覆盖 S 的充要条件：S 全部在 u 侧，S 全部在 v 侧，u, v 侧均有属于 S 的点。它将合法非树边的形态分成两类：

如上图，绿色的点表示 S，黄色的点不属于 S 但属于虚树，橙色的点不属于虚树但落在虚树上。红色虚边为合法非树边，蓝色虚边为不合法非树边。

性质 B

对于性质 B，注意到不存在跨过 d 的合法横叉边，因此可以将虚树改为我们通常所理解的虚树：若 x 有两棵子树含属于 S 的点，则 x 也属于虚树。即认为 d 属于虚树对答案无影响。

枚举 S 的 LCA d，则不存在一端在 d 子树内（不含 d），另一端在 d 子树外的（不含 d）的合法非树边。因此子树内外独立，贡献直接相乘。

设 $d$ 的所有儿子为 $s_1\sim s_k$。$s_i$ 的子树内要么没有虚树上的点，要么有虚树上的点。对于后者，根据虚树的性质，有且仅有最浅的点与 $d$ 在虚树上相连。 设 $d$ 在虚树上的儿子为 $P$，有基本贡献系数 $\prod_{p\in P} f_p$。接下来统计未考虑到的非树边： - **第一类非树边**：对于每个 $p\in P$，包含于路径 $d\rightsquigarrow p$ 的非树边。 - **第二类非树边**：对于每个 $p\in P$ 和所有 $q\in d\rightsquigarrow p$（不含 $d, p$），从 $q$ 向虚树外延伸的某条边的对应子树内的返祖边。 - **第三类非树边**：对于 $d$，向虚树外延伸且在子树内的某条边的对应子树内的返祖边。 将第三类非树边摊到每个未选点的儿子，得： - 对于选点的儿子 $s_i$，贡献系数为 $X(s_i) = \sum_{p\in \mathrm{subtree}(s_i)} g_{p\to d}$，其中 $g_{p\to d}$ 表示 $f_p$ 乘以 $2 ^ c$，其中 $c$ 表示包含于路径 $d\rightsquigarrow p$ 的非树边数量，加上对于所有 $q\in d\rightsquigarrow p$（不含 $d, p$），从 $q$ 向路径 $d\rightsquigarrow p$ 外延伸的某条边的对应子树的返祖边数量之和。 - 对于未选点的儿子 $s_i$，贡献系数为 $Y(s_i) = 2 ^ c$，其中 $c$ 表示 $s_i$ 子树内的返祖边数量 $in_{s_i}$，加上较浅的一端为 $d$，较深的一端落在 $s_i$ 子树内的返祖边数量。 ![](https://cdn.luogu.com.cn/upload/image_hosting/mv0n45o8.png) 如上图，$d$ 的左子树选择点 $p$，红色虚边为产生贡献的非树边。$d$ 的右子树没有选择，红色虚边为产生贡献的非树边。 假设已经求出 $X(s_i)$ 和 $Y(s_i)$，**考虑 $f_d$ 如何计算**。设恰好在 $k$ 棵子树内选点的答案为 $F_k$，即 $F_k = [x ^ k]\prod (X(s_i) x + Y(s_i))$。 - 如果 $d\notin S$，则至少要有两棵子树被选择，产生贡献 $\sum_{k\geq 2} F_k$。 - 如果 $d\in S$，则要求 $d$ 是关键点，对被选择子树数量没有限制，产生贡献 $-\sum_{k\geq 0} F_k$。 发现 $k\geq 2$ 的 $F_k$ 等价，因此背包时维护 $F_0, F_1$ 和 $\sum_{k\geq 2} F_{k}$ 即可。 设 $Z = \sum_{1\leq i\leq n} f_i 2 ^ {out_i}$，则 $Z = \sum_{|S|\geq 1 \ \land \ S\subseteq U} (-1) ^ {|S|} 2 ^ {c(S)}$，答案为 $-Z$。 **考虑维护 $g_{p\to d}$ 求 $X(s_i)$**。根据 $g$ 的定义，可得如下步骤： - 首先，对于 $p\in \mathrm{subtree}(d)$，令 $g_{p\to d}\gets g_{p\to s_i}$，其中 $s_i$ 是 $p$ 对应的 $d$ 的儿子。 - 对于所有 $s_i$，令 $g_{s_i\to d}\gets f_{s_i}$。由于不存在等于树边的非树边，将这一步放在下面两步之后也正确。 - 加入第一类非树边的贡献：枚举所有以 $d$ 为一端，另一端在 $d$ 子树内的非树边 $e = (d, u)$，对于 $p\in \mathrm{subtree}(u)$，将 $g_{p\to d}$ 乘以 $2$。 - 加入第二类非树边的贡献：枚举所有以 $s_i$ 为一端，另一端在 $s_i$ 子树内的非树边 $e = (s_i, u)$，设 $u$ 对应 $s_i$ 的儿子为 $v$，则对于 $s_i$ 的所有不为 $v$ 的儿子 $t_j\neq v$，对于 $p\in \mathrm{subtree}(t_j)$，将 $g_{p\to d}$ 乘以 $2$。简单地说，返祖边 $e = (u, v)$（其中 $u$ 是较浅端）会对 $u$ 的不为 $u\to v$ 后继的所有儿子的子树内所有结点产生贡献。 我使用的维护方法是：继承 $g$；加入第一类非树边的贡献；计算 $X$ 求出 $f$；加入以 $d$ 为较浅端的第二类非树边的贡献；令 $g_{d\to d} \gets f_d$。其实就是将统计第二类非树边的贡献下放到每个儿子处进行，这样好写一点，但注意这类贡献需要在计算 $X$ 求出 $f$ 之后统计。 将 $p$ 这一维用 DFS 序拍平到序列上，线段树合并维护 $g_{p\to d}$，支持区间乘法，区间求和。注意到每个子树的时间戳区间不交，所以不用线段树合并，只需用一棵线段树维护。 **考虑求 $Y(s_i)$**。在计算 $g_{p\to d}$，加入第一类非树边的贡献时，对于每个 $e = (d, u)$ 以及对应 $d$ 的儿子 $s_i$，将 $in_{s_i}$ 加上 $1$，过程结束后得到新的 $in'_{s_i}$。则 $Y(s_i) = 2 ^ {in'_{s_i}}$。 时间复杂度 $\mathcal{O}((n + m)\log n)$。 ##### 正解 相较于性质 B 多出了以 $1$ 为根时的横叉边。 考虑在何种情况下性质 B 的做法会导致错误：性质 B 保证我们可以将 $d$ 加入虚树，而性质 B 的做法在 “无论非树边是否是返祖边，只要 $d$ 在虚树上” 时，均可得到正确的答案，因为我们在分析合法非树边形态时，并没有要求这些非树边是以 $1$ 为根时的返祖边。这说明性质 B **只是** 让我们将 $d$ 加入虚树。 将 $d$ 加入虚树会导致一些非树边从合法变成不合法。 - 对于形如 “落在虚树上的点向虚树外延伸的某条边的对应子树内的返祖边” 的非树边，由于将 $d$ 加入虚树不改变落在虚树的点集，因此不会有影响。 - 对于形如 “$u, v$ 对应树上路径被虚树的某条边完全包含” 的非树边，将 $d$ 加入虚树后产生的影响为：若虚树原本不包含 $d$，且存在经过 $d$ 的虚树边 $(x, y)$，那么一条两端均属于 $x, y$ 树上路径，且两端分别在 $d$ 的两侧的非树边从合法变成了不合法。 因此，只需重新计算这样的 $S$ 的贡献：$d\notin S$，且 $d$ **恰有** 两棵子树有属于 $S$ 的点。 枚举 $d$ 和将 $d$ 加入虚树后它在虚树上的两个儿子 $p, q$，设它们分别对应 $d$ 在原树上的儿子 $u\neq v$。设 $z = g_{p\to d} \times g_{q\to d}\times \prod_{s_i \neq u, v} Y(s_i)$，这是原来计算的贡献。枚举 LCA 为 $d$ 的非树边 $e = (x, y)$，若 $x, y$ 分别在 $d\rightsquigarrow p$ 和 $d\rightsquigarrow q$ 上（路径不含 $d$，$x, y$ 顺序无关），则将 $z$ 乘以 $2$。最终得到 $z'$ 为真正的贡献。暴力做的复杂度是 $\mathcal{O}(n ^ 2 m)$。 先将 $s_i$ 子树时间戳区间的所有 $g$ 值乘以 $\frac 1 {Y(s_i)}$，最后将贡献乘以 $\prod_{s_i} Y(s_i)$（我们发现，实际上 $\prod_{s_i} Y(s_i) = 2 ^ {in_d}$），这样贡献只与 $g_{p\to d}$ 和 $g_{q\to d}$ 有关，而与其它儿子无关。 枚举 $d$，则一条 LCA 为 $d$ 的非树边的贡献是矩形乘以 $2$。若干次矩形乘以 $2$ 之后全平面求和，注意容斥掉 $u\neq v$ 的贡献。我使用的维护方法是：支持查找子树内某点 $x$ 对应的 $d$ 的儿子在时间戳上的后继 $\mathrm{suc}(x)$。扫描线，将所有儿子的时间戳加入事件，则遇到事件 $(x, l, r, c)$ 时（当前扫到时间戳 $x$，操作为给 $l\sim r$ 乘以 $c$），设上一次考虑的时间戳为 $x'$（初始值为 $d$ 的儿子时间戳最小值 $L = \mathrm{dfn}(d) + 1$）。因为所有儿子的时间戳也被加入了事件，所以 $x'\sim x - 1$ 一定是同一个儿子子树内的时间戳。求出 $x'\sim x - 1$ 的 $g$ 值之和，求出 $\mathrm{suc}(x')\sim R$ 的 $g$ 值之和（$R$ 表示 $d$ 的子树时间戳最大值 $\mathrm{dfn}(d) + \mathrm{size}(d) - 1$），相乘后再乘以 $2 ^ {out_d} \prod_{s_i} Y(s_i)$ 加入答案。 最后不要忘记将答案减去 $F_2 \times 2 ^ {out_d}$，也就是减去原先计算的错误答案。为此，需要区分 $F_2$ 和 $F_{k\geq 3}$，背包时维护 $F_0, F_1, F_2, \sum_{k\geq 3} F_{k}$。 时间复杂度 $\mathcal{O}((n + m)\log n)$，空间复杂度为 $\mathcal{O}(n + m)$，加上求 LCA 的空间复杂度。[代码](https://www.luogu.com.cn/paste/rdxgs34l)。