题目解析

问题重述

在一棵 $n$ 个节点的树上，Marat 从节点 $x$ 出发要去节点 $y$，有 $m$ 个敌人，每个敌人 $i$ 从 $a_i$ 走到 $b_i$（最短路径）。敌人在时刻 $1$ 从 $a_i$ 出发，时刻 $p$ 位于路径上的第 $p$ 个节点。Marat 也在时刻 $1$ 从 $x$ 出发，每时刻可以移动到一个相邻节点或停留。Marat 不能在任何时刻与任何敌人在同一顶点相遇（可以在边上相遇）。敌人到达 $b_i$ 后就不再存在。求 Marat 到达 $y$ 的最早时刻，或输出 $-1$。

---

关键观察

1. 答案上界

如果答案不是 $-1$，则答案 $\le 2n+1$。

证明：设最优路径为 $s_1=x, s_2, \dots, s_k=y$。在时刻 $n+1$，所有敌人都已到达工作地点（因为敌人路径长度 $\le n$）。从 $s_{n+1}$ 到 $s_k$ 最多需要 $n$ 步，所以 $k \le 2n+1$。

2. 坏时刻的定义

称 $(t, v)$ 为坏的，如果在时刻 $t$ 有敌人在顶点 $v$。

性质：所有坏时刻的总数 $\le \sum_{i=1}^m \text{len}(path(a_i, b_i)) \le n \times m$。

因为每个敌人的路径长度 $\le n$，共有 $m$ 个敌人。

---

动态规划思路

朴素 DP $O(n^2)$

定义 $dp_{v,t}$ 表示 Marat 能否在时刻 $t$ 位于顶点 $v$。

• 初始：$dp_{x,1}=1$
• 转移：如果 $dp_{v,t}=1$，则对于 $v$ 的所有邻居 $u$ 以及 $v$ 本身，$dp_{u,t+1}=1$
• 如果 $(t+1, v)$ 是坏时刻，则 $dp_{v,t+1}=0$

答案是最小的 $t$ 使得 $dp_{y,t}=1$。

优化到 $O(n \times m)$

核心思想

维护当前时刻 $t$ 可到达的顶点集合 $S_t$，而不是整个 $dp$ 表。

更新规则

从 $S_t$ 到 $S_{t+1}$：

1. 坏时刻顶点：如果 $(t+1, v)$ 是坏时刻，则 $v \notin S_{t+1}$
2. 继承：如果 $v \in S_t$，则 $v \in S_{t+1}$（可以停留）
3. 邻居传播：如果 $v$ 的某个邻居 $u \in S_t$，则 $v \in S_{t+1}$（可以从 $u$ 走过来）

两类特殊顶点

• 类型1：在时刻 $t+1$ 有敌人的顶点（坏时刻顶点）
• 类型2：不在 $S_t$ 中，但有邻居在 $S_t$ 中的顶点

---

算法实现细节

数据结构

• ok[v]：标记顶点 $v$ 是否在当前集合 $S_t$ 中
• was[v]：记录顶点 $v$ 最后一次被加入集合的时刻（用于去重）
• cur[v]：标记在下一时刻是否有敌人到达 $v$（临时标记）

处理流程

对于时刻 $t = 0, 1, 2, \dots$：

// 1. 标记当前时刻的敌人位置
if (t < block.size()) {
    for (auto &u : block[t]) cur[u] = true;
}

// 2. 找出下一时刻能到达的顶点
vi nxt;
for (auto &v : q) {  // q 是候选队列
    if (ok[v] || cur[v] || was[v] == t) continue;
    was[v] = t;
    bool nei = 0;
    for (auto &u : g[v]) nei |= ok[u];  // 检查是否有邻居在当前集合
    if (t && !nei) continue;  // 时刻 0 不需要邻居（起点特殊情况）
    nxt.push_back(v);
}

// 3. 移除当前时刻有敌人的顶点
q.clear();
if (t < block.size()) {
    for (auto &u : block[t]) {
        cur[u] = false;
        if (ok[u]) ok[u] = false;
        q.push_back(u);  // 这些顶点作为下一时刻的候选
    }
}

// 4. 添加新到达的顶点
for (auto &v : nxt) {
    ok[v] = true;
    for (auto &u : g[v]) {
        if (!ok[u]) q.push_back(u);  // 邻居作为候选
    }
}

// 5. 检查答案
if (ok[y]) {
    cout << t + 1 << '\n';
    return;
}

// 6. 终止条件
if (t > (int)block.size() && q.empty()) {
    cout << "-1\n";
    return;
}

复杂度分析

每个顶点最多可以进入集合 $m+1$ 次（每次离开后可能再次进入，最多离开 $m$ 次）。每次进入时，会将其所有邻居加入候选队列。

• 每个顶点度数之和 = $2n$
• 总候选数 $\le (m+1) \times 2n = O(n \times m)$
• 坏时刻总数 $\le n \times m$

因此总时间复杂度 $O(n \times m)$，空间复杂度 $O(n + m)$。

---

示例解释

示例1

$n=4, m=1, x=1, y=4$，敌人从 $4$ 到 $1$：

• 敌人路径：$4 \to 3 \to 2 \to 1$
• 时刻 $1$：敌人在 $4$，Marat 在 $1$
• 时刻 $2$：敌人在 $3$，Marat 可到 $2$
• 时刻 $3$：敌人在 $2$，Marat 可到 $3$
• 时刻 $4$：敌人在 $1$，Marat 可到 $4$（到达）

输出 $4$。

示例2

$n=5, m=1, x=1, y=5$，敌人从 $5$ 到 $1$：

• 如果 Marat 直接走，时刻 $2$ 在 $2$ 相遇
• 在 $1$ 等待 1 时刻：时刻 $2$ 在 $1$，时刻 $3$ 在 $2$，时刻 $4$ 在 $3$，时刻 $5$ 在 $4$，时刻 $6$ 在 $5$
• 敌人时刻 $2$ 在 $4$，$3$ 在 $3$，$4$ 在 $2$，$5$ 在 $1$，无冲突

输出 $6$。

---

总结

本题的核心技巧：

1. 利用答案上界 $2n+1$ 限制搜索范围
2. 维护可达顶点集合而非完整 DP 表
3. 利用坏时刻总数 $O(n \times m)$ 的性质
4. 每个顶点最多进入集合 $m+1$ 次，保证总复杂度 $O(n \times m)$

对于 $n \le 10^5, m \le 200$ 的数据范围，$O(n \times m) \le 2 \times 10^7$ 是可以接受的。