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

题目背景

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

问题描述

输入 ：

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

输出 ：

对于每个询问，输出满足条件的地铁线路数量。 解题思路 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] = True path.append(current) if current == target: return True for neighbor in graph[current]: if not visited[neighbor]: if dfs(neighbor, target, visited, path): return True path.pop() return False

功能

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

参数说明：

current：当前访问的节点。