当前位置：首页 > article >正文

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

article 2025/2/22 0:15:30

题目背景

小郑是一名大学生，她决定通过做志愿者来增加自己的综合分。她的任务是帮助游客解决交通困难的问题。洛斯里克城是一个六朝古都，拥有 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

功能