题目理解

我们有一个 $n$ 个点、$m$ 条边的无向图，每个点有一个标记 $0$ 或 $1$。
给定 $q$ 次询问，每次询问两个点 $x, y$ 之间是否存在一条路径（可重复经过点和边），使得路径上依次经过的点的标记连起来是一个回文串。

关键分析

1. 回文串的性质
   一个字符串是回文串，当且仅当从前往后读和从后往前读相同。
   对于路径来说，这意味着路径的标记序列必须满足对称性。

2. 路径可重复
   因为可以重复走，所以我们可以通过“绕路”来构造回文串。

3. 重要结论
   如果存在一条路径 $x \to y$ 是回文路径，那么我们可以把路径分成两半，前半段和后半段在标记上对称。
   特别地：

   • 如果路径长度是奇数（奇数个点），中间那个点可以任意。
   • 如果路径长度是偶数（偶数个点），则路径可以拆成对称的两部分。

解法思路

1. 状态表示

定义布尔数组 dp[x][y] 表示是否存在一条从 $x$ 到 $y$ 的回文路径。

2. 初始状态

• 单点路径：dp[x][x] = 1（长度为 $1$ 的串总是回文）。
• 相邻两点且标记相同：dp[x][y] = 1（长度为 $2$ 的回文串）。

3. 状态转移

如果存在 $x \to u$ 和 $y \to v$ 的边，并且 $c[u] = c[v]$，并且已知 dp[x][y] = 1，那么 dp[u][v] = 1。
这相当于在路径两端各扩展一个标记相同的点，保持回文性。

4. 图的预处理

为了高效进行上述扩展，我们需要对图进行预处理：

• 同色连通块：标记相同的点构成的连通分量。

  • 如果该连通分量是二分图，则只能走偶数长度的路径。
  • 如果该连通分量不是二分图（即存在奇环），则可以在该块内任意调整路径长度（奇偶性可调）。

• 异色边：连接不同标记的点的边，用于在不同标记的点之间扩展。

• dfs1 处理同色连通块，并检测奇环。

• dfs2 处理异色边，建立跨标记的扩展关系。

• g[x] 存储的是从 $x$ 出发可以一步到达的、在扩展中允许的邻居（包括同色块内和异色边）。

算法流程

1. 输入并存储图结构。
2. 第一次 DFS：处理同色连通块，检测奇环。如果存在奇环，就在该块内加一个自环（g[x].push_back(x)），表示可以在该点“停留”一次以改变路径奇偶性。
3. 第二次 DFS：处理异色边，建立跨标记的连接关系。
4. BFS 扩展回文路径：
   • 初始状态：所有 (x, x) 和相邻同色点对 (x, y)。
   • 每次从 (x, y) 扩展：找 x 的邻居 u 和 y 的邻居 v，如果 c[u] == c[v] 且 (u, v) 未访问过，则加入队列。
5. 回答询问：直接查 dp[x][y]。

总结

本题的关键在于：

• 将回文路径问题转化为图上的状态扩展问题。
• 利用 BFS 从已知回文路径向两端扩展。
• 预处理同色连通块的奇环性质，以支持路径奇偶性调整。
• 使用 bitset 压缩空间，提高效率。

这种方法在 $n \le 5000$ 时可以在时间和空间限制内完成。