自动搬运

查看原文

来自洛谷，原作者为

	AFewSuns 弱省弱校蒟蒻，tcl，zbl

搬运于2025-08-24 22:53:55，当前版本为作者最后更新于2024-01-16 17:37:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

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

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

---

题目大意

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

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

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

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

$1 \leq T \leq 10,2 \leq n \leq 18$。

题目分析

先考虑如何做 $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))$

2. $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 树上每个节点的边集去重；不难证明一定存在最优方案使得每条链都有端点是叶子。

提交记录