题解

问题分析

题目要求判断Tom在初始位置$(a_i, b_i)$下是否一定能在有限次行动中抓住Jerry。核心矛盾在于：Jerry可沿任意多条边移动（但不能经过Tom当前位置），而Tom每次最多移动一条边。Tom的目标是缩小距离抓住Jerry，Jerry则需无限躲避。

关键洞察

1. Jerry的躲避条件：Jerry能永远躲避的核心是存在“安全区域”——通常是含环的双连通分量（2-连通分量）。在环中，Jerry可通过绕圈始终与Tom保持距离，而Tom因每次移动受限无法追上。
2. Tom的必胜条件：若Jerry所在的区域（或可到达的区域）不存在这样的安全环，或Tom能封锁所有逃生路径，则Tom必胜。
3. 图结构的影响：无向图的双连通分量（块）是分析的关键。双连通分量中，任意两点间有至少两条独立路径（即含环），而桥连接的分量则是树状结构（无环）。

算法步骤

1. 双连通分量分解（Tarjan算法）：
   用Tarjan算法将原图分解为双连通分量（块），每个块是极大的2-连通子图（含环）或桥。构建块-点树（圆方树）：将原图顶点作为“圆点”，每个双连通分量作为“方点”，圆点与所属方点相连，形成树结构（块-点树无环，便于树形分析）。

2. 块-点树预处理：
   对块-点树计算深度、祖先（LCA的二进制 lifting 表）、欧拉序（L/R数组，用于判断祖先-子孙关系），为后续查询提供高效支持。

3. 安全区域标记：
   通过多次DFS（dfs2、dfs3等）标记“安全块”（Jerry可在此无限躲避）和“可控块”（Tom可封锁的区域）。具体来说：

   • 若块是双连通分量（含环），可能成为安全区域；
   • 若块是桥连接的树状结构，Tom更易控制。

4. 查询判定（check函数）：
   对每个初始位置$(a, b)$，通过块-点树的结构判断：

   • 若Jerry所在区域不存在安全块，或Tom能通过移动封锁所有安全块，则输出“Yes”；
   • 否则输出“No”。

代码解析

• 双连通分量分解（dfs函数）：用Tarjan算法的dfn（访问时间）和low（最低可达时间）标记双连通分量，将每个分量作为方点（编号从$n+1$开始），构建块-点树G。
• 树结构预处理（dfs1）：计算块-点树的深度、祖先表（用于LCA查询）和欧拉序（L/R数组），支持快速判断节点包含关系。
• 安全区域标记（dfs2、dfs3）：vis1标记方点是否为安全块，vis标记圆点是否处于可控区域，通过递归判断块的安全性。
• 查询判定（check函数）：利用LCA和欧拉序判断$b$（Jerry初始位置）是否处于Tom可控的区域，输出结果。

复杂度分析

• 时间复杂度：$O(n + m + q \log n)$。双连通分量分解为$O(n + m)$，块-点树预处理（含LCA）为$O(n \log n)$，每次查询通过LCA判断为$O(\log n)$。
• 空间复杂度：$O(n + m)$，用于存储图、块-点树及各类标记数组。

综上，算法通过双连通分量分解将原图转化为树结构，利用树的性质分析安全区域，高效判定Tom的必胜性，适用于大规模图数据。