【题解】P10017 [集训队互测 2023] Axium Crisis

· · 题解

终于加强了，很高兴！来水一篇题解。

不一定会更好的阅读体验。

题目大意

给定一颗 n 个点的树，节点编号为 0\sim n-1。

边有边权，边权为 0 或 1 或不确定。

你要给每条未被确定边权的边确定一个 0 或 1 的边权，然后从树上取出若干条有向路径，使得这些链两两之间满足边不相交。

然后你会把这些路径插入一颗 01-Trie，你希望最大化这颗 01-Trie 上的节点数。需要输出方案。

### 题目分析 先考虑如何做 $w\in \{0,1\},c=0$。 拿出树上的每一条有向路径，将它们按照字典序排序，那么原问题变成从中选出若干条边不相交的路径，它们的权值为长度之和减去相邻两项 $\operatorname{lcp}$，求权值最大值。 直接从前往后 dp，设 $f_{i,S}$ 表示只考虑前 $i$ 条路径，选了第 $i$ 条路径，且当前选取的路径边集并为 $S$ 的最大权值。转移时枚举上一个选的是什么，时间复杂度 $\mathcal O(n^42^n)$。 设字典序第 $i$ 小的字符串为 $s_i$，那么 $\operatorname{lcp}(s_i,s_j)=\min\limits_{i \leq k < j}{\operatorname{lcp}(s_k,s_{k+1})}$。于是就可以一步步转移了，设 $f_{i,S,j}$ 表示考虑了前 $i$ 条路径，选取的边集并为 $S$，且当前路径与上一个选择的路径的 $\operatorname{lcp}$ 为 $j$ 的答案。转移如下： 1. $f_{i-1,S,j} \to f_{i,S,\min(j,\operatorname{lcp}(s_{i-1},s_i))}$，预转移，处理一下 $\operatorname{lcp}$； 2. $f_{i-1,S,j}+len_i-j \to f_{i,S\cup E_i,len_i}(S\cap E_i= \emptyset)$，表示选第 $i$ 条路径，其中 $E_i$ 表示第 $i$ 条路径的边集，$len_i$ 表示第 $i$ 条路径的字符串长度。 时间复杂度 $\mathcal O(n^32^n)$，需要滚动数组优化空间。字符串排序直接塞 trie 里就行了。 --- 然后考虑 $w\in \{0,1,2\},c=0$。 当所有 $w\neq 2$ 时，每条边都是确定的，所以总共只会有 $n(n-1)$ 个串；而当存在 $w=2$ 时，需要枚举边集的所有情况，这样可能会有 $\mathcal O(n^22^n)$ 个串。 实际上只会有 $\mathcal O(2^n)$ 个串。考虑剥叶子，第一个次剥的叶子最多往外连 $2\times (2^1+\cdots+2^{n-1})<2^{n+1}$ 个串，乘 $2$ 是因为路径有向。而第二次剥的叶子最多往外连 $2^n$ 个串，以此类推，所以最后不会超过 $2^{n+2}$ 个串，即 $\mathcal O(2^n)$。 然后优化一下转移，第一维完全可以不记，让 $f$ 数组自转： 1. $f_{S,j} \to f_{S,\operatorname{lcp}(s_{i-1},s_i)}(j>\operatorname{lcp}(s_{i-1},s_i))
  1. f_{S/E_i,j}+len_i-j \to f_{S,len_i}(E_i \subseteq S)

当然 i 还是要枚举的，这样就不担心空间了。考虑分析时间复杂度。

对于第 2 部分，考虑树上一条长度为 len 的路径 x\to y，它中间最多会产生 2^{len} 个串，其中每个串都要枚举 2^{n-1-len} 个超集，于是它们的总转移时间复杂度为 \mathcal O(n2^n)。有 \mathcal O(n^2) 对 (x,y)，所以总转移时间复杂度就是 \mathcal O(n^32^n) 的。

对于第 1 部分，考虑只保留有用的 dp 状态。将每次通过第 2 步转移得到的 dp 状态为“关键状态”，由上面可知“关键状态”只有 \mathcal O(n^22^n) 个，而每个关键状态经过第 1 步转移时第二维至少减 1，所以最多经过 n 次第一步转移，于是总转移时间复杂度就是 \mathcal O(n^32^n) 的了！

大概需要精细实现，当然不那么精细也可以，毕竟卡不满。

之后考虑 c=1，即如何构造方案。

显然不能开一个 \mathcal O(n4^n) 的数组记录从哪转移过来的，不然就又退化了。

于是考虑用一个操作栈来维护有效的 dp 转移，之后从后往前推就可以得到方案了。

直接记录的空间复杂度为 \mathcal O(n^32^n)，不可接受。考虑再分析一下有效状态数。

对于转移的第 2 部分，容易发现在枚举超集 S 后可以不用对每个 f_{S/E_i,j} 都尝试转移 f_{S,len_i}，直接取最大值记录在栈里就行了，空间复杂度 \mathcal O(n^22^n)；

而对于第 1 部分，考虑树上一条长度为 len 的路径 x\to y，最坏情况下中间会有 2^{len} 个串，其分布在 trie 树上的第 len 层。模拟一下这些串在第 1 部分贡献的转移复杂度，发现在遍历每个串的时候会先转移到所有 f_{S,len}，其中 S 为这条路径的超集；之后根据先前的复杂度分析，这些 f_{S,len} 最多在第 1 部分转移 n 次，于是就有先前分析的复杂度。

实际上，对于 trie 树第 len 层的前两个节点，遍历完它们之后，它们转移到的“关键状态”是完全相等的！换句话说，由于 dp 转移是取 \max，所以对于每个 S，这两个节点对应的“关键状态”都是 f_{S,len}，通过取 \max 合并到一个状态了，于是它们总的复杂度贡献是 n。

同理，对于 trie 树上第 i 层的一个节点，它下面有 2^{len-i} 个第 len 层的节点，这些节点对应的“关键状态”在第二维减到 i 的时候就全合并成一个 dp 状态了（对不同的超集 S 而言）。于是实际上 x\to y 的这些串在第 1 部分贡献的总复杂度为它们在 trie 上的虚树大小（对不同的超集 S 而言），即 \mathcal O(2^{len})。而总共有 2^{n-1-len} 个超集，于是时间复杂度就是 \mathcal O(2^n)，所有 (x,y) 的总时间复杂度就是 \mathcal O(n^22^n)，空间复杂度也就变成 \mathcal O(n^22^n) 的了。

时间复杂度 \mathcal O(n^32^n)，空间复杂度 \mathcal O(n^22^n)。实际上栈的大小大概开 2\times 10^7 就够了，然后时间空间复杂度写得没那么精细也能过。

以上是原题部分，考虑继续优化。

不难发现现在唯一的复杂度瓶颈在于第 2 步转移，需要枚举超集 S 后再枚举 j\in [0,n-1] 进行转移。但其实只需要对于每个 S，维护出 g_S 表示 f_{S,j}-j 最大的 j 就行了，由于 dp 值只会变大，所以是很好维护的。时空复杂度 \mathcal O(n^22^n)。

不难精细实现。栈的大小开 3\times 10^6 就够了。

一些剪枝：对 trie 树上每个节点的边集去重；不难证明一定存在最优方案使得每条链都有端点是叶子。

提交记录