题解

思路

把不能再拆成两条非空好路径的部分称为极小块。每个极小块记录五元组 $(x,y,\ell,p,q)$：起点、终点、长度，以及幻觉是否覆盖起点和终点。幻觉为空的单边块记为 $p=q=0$。

若一条边 $u\to v$ 的幻觉中相邻出现 $u,v$，可从这对位置分别向左右沿图唯一扩展，得到两端都覆盖的极小块；幻觉末尾等于起点或开头等于终点时，同理得到只覆盖一端的极小块。

做法

子任务 1

生成全部极小块后，从每个覆盖起点的块出发，递归枚举所有可拼接块序列，长度超过 $2n$ 即停止。两个块可以拼接，当且仅当前块的 $q$ 与后块的 $p$ 异或为一。该算法在小图上完整枚举所有组合。

子任务 2

用 $F[s][u][i][q]$ 记录起点为 $s$、当前终点为 $u$、长度为 $i$、末端覆盖标记为 $q$ 的方案数。按长度递增转移，显式保留起点维度，避免指数枚举。

子任务 3

最终答案不区分起点，因此可直接在初始化时合并起点维度。令 $f[u][i][q]$ 表示当前终点、长度和末端标记，遍历从 $u$ 出发且首端标记与 $q$ 异或为一的极小块。每个好路径按其极小块分解唯一计数。

复杂度

子任务 1 与实际块分支数有关，为指数级枚举；子任务 2 为 $O(n^2B)$；满分算法为 $O(nB)$，其中 $B$ 是生成的极小块数，且生成阶段总计 $O(nm+\sum k_i)$。空间复杂度分别为递归栈与块表、$O(n^3+B)$、$O(n^2+B)$。

正确性说明

任意非空好路径中，至少有一条街道的幻觉包含与该街道端点对应的相邻位置；从该位置向两端扩展得到一个极小块。其余部分只能通过空幻觉边或恰好覆盖一个连接端点的块拼接，拼接条件正是两端覆盖标记异或为一。反之，满足该条件的块序列在连接点处现实商店恰被幻觉覆盖一次，拼接后仍是好路径。因此极小块序列与好路径一一对应，三档算法只是分别枚举、保留或合并起点维度，计数均正确。