T30669: 地铁换乘

LCA（最近公共祖先）和倍增法（Binary Lifting）, http://cs101.openjudge.cn/practice/30669/

B 市有 n 个地点，编号为 1 ~ n，可视为根节点为编号 t 的树，交通管理局在根节点上。

记每个节点的深度为其到 t 的边数，如根节点 t 的深度为 0。

作为交通管理局局长的小 W 计划修一趟地铁，线路 A 从编号为 p 的地点出发，线路 B 从编号为 q 的地点出发，修线路 A 的施工队 1 速度为一天修 v1 条边，修线路 B 的施工队 2 速度为一天修 v2 条边，而小 W 想构建一个换乘站，所以他指挥施工队 1 从 p 出发往 q 修，施工队 2 从 q 出发往 p 修，数据保证某一天他们一定会在一个节点相遇，该节点即为换乘站。

小 W 想知道多少天后两个施工队会相遇，并且小 W 想知道换乘站的深度，以便于他能及时地从交通管理局赶到换乘站。

数据范围：1 ≤ n ≤ 2×10^5, 1 ≤ t,p,q ≤ n, 1 ≤ v1,v2 ≤ 10^9, 1 ≤ u,v ≤ n,u≠v

保证输入构成一棵树。保证 p 到q 的距离L 满足 L mod (v1+v2) = 0。

保证相遇点一定在某个节点上，且相遇天数为整数。

输入

第一行两个正整数 n,t，代表地点个数与根节点编号。

接下来 n-1 行，每行两个正整数 u,v，代表编号为 u,v 的两个地点相连。

接下来一行四个正整数 p,q,v1,v2，分别代表施工队 1、施工队 2 的出发节点与施工速度。

输出

一行用空格隔开的两个正整数，分别代表相遇天数与换乘站深度。

样例输入

样例输出

1 1

提示

LCA（最近公共祖先）和倍增法（Binary Lifting）

来源

2026 ZHAIBoen

python

import sys

# 增加递归深度
sys.setrecursionlimit(200000)

def solve():
    # 读取 n 和 根节点 t
    try:
        line1 = sys.stdin.readline().split()
        if not line1: return
        n, t = map(int, line1)
    except ValueError: return

    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        adj[v].append(u)

    p, q, v1, v2 = map(int, sys.stdin.readline().split())

    # 倍增预处理
    LOG = 18  # 2^18 > 200,000
    depth = [0] * (n + 1)
    up = [[0] * LOG for _ in range(n + 1)]

    def dfs(u, fa, d):
        depth[u] = d
        up[u][0] = fa
        for v in adj[u]:
            if v != fa:
                dfs(v, u, d + 1)

    dfs(t, 0, 0)

    # 构建倍增表
    for i in range(1, LOG):
        for u in range(1, n + 1):
            if up[u][i-1] != 0:
                up[u][i] = up[up[u][i-1]][i-1]

    # 求 LCA 函数
    def get_lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        # 爬升到同一深度
        diff = depth[u] - depth[v]
        for i in range(LOG):
            if (diff >> i) & 1:
                u = up[u][i]
        if u == v:
            return u
        # 同时向上跳
        for i in range(LOG - 1, -1, -1):
            if up[u][i] != up[v][i]:
                u = up[u][i]
                v = up[v][i]
        return up[u][0]

    # 求第 k 个祖先
    def get_kth_ancestor(u, k):
        for i in range(LOG):
            if (k >> i) & 1:
                u = up[u][i]
        return u

    # 1. 计算 LCA 和 距离
    r = get_lca(p, q)
    dist_p_r = depth[p] - depth[r]
    dist_q_r = depth[q] - depth[r]
    L = dist_p_r + dist_q_r

    # 2. 计算天数
    days = L // (v1 + v2)

    # 3. 找到相遇节点
    dist_from_p = v1 * days
    if dist_from_p <= dist_p_r:
        # 相遇点在 p 到 LCA 的链上，是 p 的祖先
        meeting_node = get_kth_ancestor(p, dist_from_p)
    else:
        # 相遇点在 q 到 LCA 的链上，是 q 的祖先
        dist_from_q = v2 * days
        meeting_node = get_kth_ancestor(q, dist_from_q)

    print(f"{days} {depth[meeting_node]}")
    # 如果想知道编号，打印 meeting_node 即可

# 示例运行
if __name__ == "__main__":
    solve()

这是一道典型的树上路径与距离计算问题。虽然提示提到了 LCA（最近公共祖先） 和 倍增法，但正如你所发现的，在保证“相遇点一定在节点上”且“路径唯一”的树结构中，使用 BFS（广度优先搜索） 同样可以有效解决，且逻辑更直观。

题目解读

树结构： $n$ 个点 $n - 1$ 条边，连通且无环。 $t$ 为根，决定了每个点的“深度”。
相遇逻辑： $p$ 和 $q$ 之间只有唯一的一条路径。施工队 1 从 $p$ 出发，施工队 2 从 $q$ 出发，速度分别为 $v 1, v 2$ 。
关键公式：
- 设 $p$ 到 $q$ 的路径长度（边数）为 $L$ 。
- 相遇天数 $T = \frac{L}{v 1 + v 2}$ 。
- 换乘站位置：从 $p$ 沿着往 $q$ 的路径走 $v 1 \times T$ 步（或者从 $q$ 往 $p$ 走 $v 2 \times T$ 步）。

优化思路

原代码使用了多次 BFS 且逻辑略显复杂（标记节点再寻找交点）。我们可以将其优化为 两次 BFS：

第一次 BFS（从根节点 $t$ 出发）：遍历全树，记录每个节点到 $t$ 的深度（depth）。
第二次 BFS（从起点 $p$ 出发）：寻找终点 $q$ 。在 BFS 过程中，记录每个节点的前驱节点（parent）。这样找到 $q$ 后，可以通过前驱节点回溯，直接还原出 $p$ 到 $q$ 的唯一路径。
计算与输出：利用回溯得到的路径找到换乘站，并输出其天数和深度。

优化后的代码（Python）

python

import sys
from collections import deque

# 增加递归深度限制（虽然用BFS不需要，但处理树结构建议养成习惯）
sys.setrecursionlimit(300000)

def solve():
    # 使用快速读取，处理大规模数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    idx = 0
    n = int(input_data[idx]); idx += 1
    t = int(input_data[idx]); idx += 1
    
    # 1. 构建邻接表
    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
        
    p = int(input_data[idx]); idx += 1
    q = int(input_data[idx]); idx += 1
    v1 = int(input_data[idx]); idx += 1
    v2 = int(input_data[idx]); idx += 1

    # 特殊情况：出发点相同
    if p == q:
        # 第一次BFS获取深度
        depth_t = get_depth(n, t, adj)
        print(0, depth_t[p])
        return

    # 2. 第一次 BFS：从根节点 t 出发，计算所有节点的深度
    depths = [-1] * (n + 1)
    depths[t] = 0
    queue = deque([t])
    while queue:
        curr = queue.popleft()
        for neighbor in adj[curr]:
            if depths[neighbor] == -1:
                depths[neighbor] = depths[curr] + 1
                queue.append(neighbor)

    # 3. 第二次 BFS：从 p 出发找到 q，并记录路径前驱
    # parent_p[v] 表示在以 p 为起点的搜索树中 v 的父节点
    parent_p = [0] * (n + 1)
    dist_p = [-1] * (n + 1)
    dist_p[p] = 0
    queue = deque([p])
    
    found_q = False
    while queue:
        curr = queue.popleft()
        if curr == q:
            found_q = True
            break
        for neighbor in adj[curr]:
            if dist_p[neighbor] == -1:
                dist_p[neighbor] = dist_p[curr] + 1
                parent_p[neighbor] = curr
                queue.append(neighbor)
        if found_q: break

    # 4. 计算相遇天数和换乘站
    L = dist_p[q]             # p 到 q 的总距离
    days = L // (v1 + v2)      # 相遇天数
    dist_from_q = v2 * days   # 换乘站距离 q 的步数
    
    # 从 q 开始沿着前驱数组往回走 dist_from_q 步，找到换乘站
    transfer_station = q
    for _ in range(dist_from_q):
        transfer_station = parent_p[transfer_station]
        
    # 输出结果：相遇天数 换乘站深度
    print(f"{days} {depths[transfer_station]}")

def get_depth(n, t, adj):
    """辅助函数：单独计算深度"""
    depths = [-1] * (n + 1)
    depths[t] = 0
    dq = deque([t])
    while dq:
        u = dq.popleft()
        for v in adj[u]:
            if depths[v] == -1:
                depths[v] = depths[u] + 1
                dq.append(v)
    return depths

if __name__ == "__main__":
    solve()

核心优化点解读：

数据结构优化：
- 将 dict() 改为 list 嵌套 list 的邻接表。在 $N = 2 \times 10^{5}$ 的量级下，列表的索引访问比字典的哈希查找快得多，且内存占用更低。
- 使用 sys.stdin.read().split() 一次性读取数据，避免多次调用 input() 产生的 I/O 耗时。
算法逻辑简化：
- 路径回溯法：不再使用“多个 BFS 标记交点”的方法。在从 $p$ 到 $q$ 的 BFS 过程中，我们顺便记录了每个点的“爸爸”是谁（parent_p）。
- 一旦找到了 $q$ ，我们知道 $p \to q$ 的距离是 $L$ ，那么换乘站就在距离 $q$ 点 $v_{2} \times T$ 步的位置。我们只需要拿着 parent_p 数组，从 $q$ 开始往回跳即可。这样直接定位，省去了后半段复杂的标记比对过程。
时间复杂度分析：
- 两次 BFS 均为 $O (N)$ 。
- 路径回溯最多 $O (N)$ 。
- 总体复杂度 $O (N)$ ，对于 $2 \times 10^{5}$ 的数据规模，可以在 1 秒左右完成计算，非常稳健。

关于倍增法的提示：

题目提到“倍增法”，是因为在标准的树算法中，求 $p, q$ 的距离通常用 LCA： $d i s t (p, q) = d e p t h (p) + d e p t h (q) - 2 \times d e p t h (L C A (p, q))$ 。然后用倍增向上跳。但由于本题只需要求一次路径，直接 BFS 反而更简单直接。如果题目要求查询成千上万对不同的 $p, q$ ，那么倍增法才是必须的。

T30669: 地铁换乘 ​

T30669: 地铁换乘