（蓝桥杯——10. 小郑做志愿者）洛斯里克城志愿者问题详解

题目背景

小郑是一名大学生，她决定通过做志愿者来增加自己的综合分。她的任务是帮助游客解决交通困难的问题。洛斯里克城是一个六朝古都，拥有 N 个区域和古老的地铁系统。地铁线路覆盖了树形结构上的某些路径，游客会询问两个区域是否可以通过某条地铁线路直达，以及有多少条这样的线路。小郑需要快速回答这些问题，否则可能会失去志愿者工时。

---

问题描述

1. 输入 ：

   • N: 洛斯里克城的区域数。
   • M: 地铁线路的数量。
   • Q: 游客的询问数量。
   • N−1 条轨道：连接 N 个区域形成一棵树。
   • M 条地铁线路：每条线路覆盖树上某两点之间的最短路径。
   • Q 个游客询问：每个询问给出两个区域 (p,q)，问它们是否在某条地铁线路上，如果是，统计有多少条这样的线路。

2. 输出 ：

   • 对于每个询问，输出满足条件的地铁线路数量。

---

解题思路

1. 树的基本性质

洛斯里克城的区域构成了一棵树（无环连通图），具有以下性质：

• 任意两点之间有且仅有一条简单路径。
• 可以通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历树，计算每个节点的深度和父节点关系。
• 最近公共祖先（LCA）可以帮助我们快速找到两点之间的路径。

2. 地铁线路的路径覆盖

每条地铁线路覆盖了树上某两点之间的最短路径。为了判断某个点对 (p,q) 是否被某条地铁线路覆盖，我们需要：

• 找到地铁线路的起点和终点。
• 计算这条线路覆盖的所有点对，并记录这些点对被多少条地铁线路覆盖。

3. 游客询问的处理

对于每个询问 $(p, q)$：

• 如果 p>q，交换 p 和 q，确保点对有序。
• 查询点对 (p,q) 被多少条地铁线路覆盖。

---

算法设计

方法一：

1. 构建树结构

代码

graph = defaultdict(list)for _ in range(N - 1):u, v = map(int, input().strip().split())graph[u].append(v)graph[v].append(u)

功能

• 使用 defaultdict(list) 构建无向图的邻接表。

• 每条轨道连接两个区域 u 和 v，因此需要将 v 添加到 u 的邻居列表中，同时将 u 添加到 v 的邻居列表中。

示例

假设输入如下轨道信息：

复制

1 2

2 3

1 4

构建的邻接表为：

作用

• 邻接表表示了树的结构，方便后续通过 DFS 找到任意两点之间的路径。

---

2. 存储地铁线路

代码

subway_lines = []for _ in range(M):a, b = map(int, input().strip().split())subway_lines.append((a, b))

功能

• 将每条地铁线路的起点 a 和终点 b 存储为元组 (a, b)，并添加到列表 subway_lines 中。

示例

假设输入如下地铁线路：

作用

• 地铁线路的起点和终点用于后续查找路径覆盖情况。

---

3. 深度优先搜索（DFS）

代码

def dfs(current, target, visited, path):visited[current] = Truepath.append(current)if current == target:return Truefor neighbor in graph[current]:if not visited[neighbor]:if dfs(neighbor, target, visited, path):return Truepath.pop()return False

功能

• 使用递归实现深度优先搜索（DFS），从起点 current 开始，找到目标节点 target 的路径。

• 参数说明：

  • current：当前访问的节点。