题目重述

• 给定一棵 $N$ 个节点的树。
• 有 $M$ 个囚犯，第 $j$ 个囚犯起点 $S_j$，终点 $T_j$。
• 每个囚犯必须沿唯一最短路径从 $S_j$ 到 $T_j$。
• 每次只能移动一个囚犯到相邻房间，且目标房间不能有其他人。
• 问是否存在一种移动顺序，使得所有囚犯都能到达目的地。

核心难点

囚犯的路径在树上可能交叉或部分重叠，如果两个囚犯的路径有公共点（非同时作为起点/终点），则必须错开时间通过，否则会违反“房间只能有一个人”的规则。这种先后顺序会形成约束关系，若约束成环，则无解。

关键观察

1. 路径相交的类型

对于两个囚犯 $i$ 和 $j$：

1. $S_j$ 在 $i$ 的路径上
   囚犯 $i$ 要经过 $S_j$，必须等囚犯 $j$ 离开 $S_j$ 之后才能经过。
   ⇒ 约束：$i$ 必须在 $j$ 之后经过 $S_j$，即 $i \to j$（$i$ 依赖 $j$ 先离开）。

2. $T_j$ 在 $i$ 的路径上
   囚犯 $i$ 要经过 $T_j$，必须在囚犯 $j$ 到达 $T_j$ 之前经过，否则 $j$ 到达后 $T_j$ 就有人了，$i$ 不能再进入。
   ⇒ 约束：$j$ 必须在 $i$ 之后经过 $T_j$，即 $j \to i$（$j$ 依赖 $i$ 先离开）。

3. 路径有公共边
   这其实已经隐含在上面两种情况中，因为公共边的端点必然在两条路径上，会触发上述规则。

2. 依赖图模型

我们可以建立一个有向图 $G$：

• 节点：$M$ 个囚犯。
• 边：根据上述两种规则添加有向边。
  • 若 $S_j \in \text{Path}(S_i, T_i)$，则加边 $i \to j$。
  • 若 $T_j \in \text{Path}(S_i, T_i)$，则加边 $j \to i$。

定理：原问题有解 ⇔ 该依赖图无环。

3. 为什么有环就无解？

假设存在环 $a_1 \to a_2 \to \dots \to a_k \to a_1$。

• $a_1 \to a_2$ 表示 $a_1$ 必须在 $a_2$ 离开 $S_{a_2}$ 之后才能经过 $S_{a_2}$。
• $a_2 \to a_3$ 表示 $a_2$ 必须在 $a_3$ 离开 $S_{a_3}$ 之后才能经过 $S_{a_3}$。
• ...
• $a_k \to a_1$ 表示 $a_k$ 必须在 $a_1$ 离开 $S_{a_1}$ 之后才能经过 $S_{a_1}$。

这样形成循环等待，无法安排谁先走，因此无解。

算法步骤

1. 预处理树的 LCA，支持 $O(\log N)$ 判断一个点是否在一条路径上。
2. 对每对囚犯 $(i, j)$：
   • 检查 $S_j$ 是否在 $i$ 的路径上，若是则加边 $i \to j$。
   • 检查 $T_j$ 是否在 $i$ 的路径上，若是则加边 $j \to i$。
3. 在 $M$ 个点的有向图上检查环（拓扑排序 / DFS）。
4. 无环输出 Yes，有环输出 No。

复杂度与优化

• 朴素实现：$O(M^2 \log N)$，在 $M$ 较大时不可行。
• 优化：
  对每个囚犯 $i$，我们想知道路径 $S_i \to T_i$ 上是否有其他囚犯的 $S_j$ 或 $T_j$。
  可以用树上差分 + DFS 序区间查询，把所有 $S_j, T_j$ 标记在树上，然后对路径做查询，这样可降到 $O((N+M)\log N)$。

总结

这道题的关键是将移动冲突转化为有向图的依赖关系，并判断依赖图是否是有向无环图 (DAG)。
只要理解“起点在别人路径上”和“终点在别人路径上”产生的两种约束，就能建立模型，从而用图论方法解决。