衢江网站建设百度快照提交入口
题目背景
小郑是一名大学生，她决定通过做志愿者来增加自己的综合分。她的任务是帮助游客解决交通困难的问题。洛斯里克城是一个六朝古都，拥有 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] = 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：当前访问的节点。
-