题意理解

Tom 和 Speike 在一棵 $n$ 个节点的树上进行追逐游戏：

• 初始位置：Tom 在 $a$，Speike 在 $b$（$a \neq b$）
• Tom 先手，双方轮流移动或停留
• 如果某次行动后双方在同一位置，Speike 获胜
• Tom 建造了 $m$ 条额外边（只有 Tom 能走）

求所有 $n \times (n-1)$ 个起始点对中，Tom 有必胜策略的点对数量。

核心思路

关键观察 1：基础博弈分析

在只有树边的原始情况下：

• 如果初始距离 $dist(a,b)$ 为奇数：Tom 必败
• 如果初始距离 $dist(a,b)$ 为偶数：Tom 可采用镜像策略必胜

镜像策略：Tom 总是保持与 Speike 的距离不变或增加，避免被抓住。

关键观察 2：额外边的影响

额外边为 Tom 提供了逃生通道，彻底改变了博弈局面：

• 距离重置：Tom 可通过额外边瞬间改变位置
• 时间优势：Tom 可能比 Speike 更早到达某些关键位置
• 循环逃避：Tom 可利用额外边建立不败的移动循环

关键观察 3：Tom 的必胜条件

Tom 必胜当且仅当存在节点 $v$ 满足：

$$D_{G'}(a, v) < D_{tree}(b, v)$$

其中：

• $D_{G'}(a, v)$：Tom 从 $a$ 到 $v$ 的最短路径（可使用额外边）
• $D_{tree}(b, v)$：Speike 从 $b$ 到 $v$ 的最短路径（只能走树边）

算法框架

方法一：可达性分析

对于每个 Speike 的起点 $b$：

1. 预处理：

   • 以 $b$ 为根，计算树上每个节点到 $b$ 的距离 $D_{tree}[u]$
   • 在扩展图 $G'$（树+额外边）上，计算从每个节点到 $b$ 的最短距离 $D_{G'}[u]$

2. 统计必胜点对：

   • 对于每个 Tom 的起点 $a$，检查是否存在 $v$ 使得：$$D_{G'}[a] + D_{G'}[v] < D_{tree}[v]$$
   • 这表示 Tom 可以比 Speike 更早到达 $v$

方法二：关键点优化

利用额外边的端点作为关键点：

1. 关键点识别：所有额外边的端点构成关键点集合 $K$
2. 距离预处理：
   • 对每个关键点 $k \in K$，计算到所有节点的最短距离
   • 使用多源 BFS 或 Dijkstra 算法
3. 快速判断：对于点对 $(a,b)$，Tom 必胜当且仅当存在关键点 $k$ 使得：$$D_{G'}(a,k) < D_{tree}(b,k)$$

方法三：对称性利用

由于需要统计所有点对，可以利用对称性：

• 固定 $b$，批量计算所有 $a$ 的胜负情况
• 使用数据结构（如线段树、并查集）维护可达关系
• 通过离线处理优化复杂度

复杂度分析

直接暴力

• 对每个点对 $(a,b)$ 单独判断：$O(n^2 \times \text{查询时间})$
• 不可接受（$n \leq 10^5$）

优化目标

• 预处理：$O((n+m) \log n)$
• 批量统计：$O(n \log n)$ 或 $O(n \sqrt{n})$
• 总体：$O(n \log n + m \log n)$

实现细节

图存储与遍历

• 使用邻接表存储树和额外边
• BFS 用于树上距离计算
• Dijkstra 或 0-1 BFS 用于带额外边的距离计算

关键点处理

# 关键点优化伪代码
key_points = set()
for edge in extra_edges:
    key_points.add(edge.u)
    key_points.add(edge.v)

# 多源最短路
dist_from_keys = multi_source_bfs(key_points, graph)

胜负判断优化

对于固定 $b$：

1. 计算 $b$ 到所有节点的树距离
2. 建立数据结构，支持查询：是否存在关键点 $k$ 使得 $D_{G'}(a,k) < D_{tree}(b,k)$
3. 使用排序 + 双指针或线段树批量处理

特殊情况分析

$m = 0$（无额外边）

• 直接统计距离为偶数的点对数量
• 答案 = 满足 $dist(a,b) \equiv 0 \pmod{2}$ 的点对数

$m = 1$（子任务5）

• 只有一条额外边，情况相对简单
• 可以分类讨论额外边连接的各种情况

树为链状结构

• 具有更强的单调性
• 可能有多项式时间解法

总结

本题的核心在于：

1. 博弈转化：将胜负条件转化为图上的距离比较问题
2. 额外边利用：分析 Tom 如何通过额外边获得时间优势
3. 批量处理：高效统计所有起始点对的胜负情况
4. 关键点优化：利用额外边的端点简化判断条件

这是一个典型的图论 + 博弈论综合问题，考察选手对图算法和博弈分析的深入理解，体现了集训队互测题目的高难度和综合性。