T30830: 地铁换乘（多组查询版）

倍增法，http://cs101.openjudge.cn/practice/30830/

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

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

有 m 次询问，每次给出两个起点 p,q 与速度 v1,v2：

线路 A 施工队从 p 出发往 q 修，每天修 v1 条边；

线路 B 施工队从 q 出发往 p 修，每天修 v2 条边。

数据保证：

p 到 q 的路径长度 L 满足 Lmod(v1+v2)=0，

两队一定在某个整点、某个节点相遇，该节点为换乘站。

对每次询问，输出：相遇需要的天数、换乘站的深度。

数据范围：1 ≤ n, m ≤ 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，表示两点连边。

接下来一行一个正整数 m，表示询问组数。

接下来 m 行，每行四个正整数 p,q,v1,v2。

输出

共 m 行，每行两个整数：相遇天数、换乘站深度。

样例输入

样例输出

1 1

提示

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

来源

http://cs101.openjudge.cn/practice/30669/

python

import sys
input = sys.stdin.read
data = input().split()

def main():
    ptr = 0
    n, t = int(data[ptr]), int(data[ptr+1])
    ptr += 2

    # 建图
    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = int(data[ptr])
        v = int(data[ptr+1])
        adj[u].append(v)
        adj[v].append(u)
        ptr += 2

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

    # DFS 初始化
    stack = [(t, 0, 0)]
    while stack:
        u, fa, d = stack.pop()
        depth[u] = d
        up[u][0] = fa
        for v in adj[u]:
            if v != fa:
                stack.append((v, u, d + 1))

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

    # LCA
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        # 对齐深度
        for j in range(LOG-1, -1, -1):
            if depth[u] - (1 << j) >= depth[v]:
                u = up[u][j]
        if u == v:
            return u
        for j in range(LOG-1, -1, -1):
            if up[u][j] != up[v][j]:
                u = up[u][j]
                v = up[v][j]
        return up[u][0]

    # 第 k 个祖先
    def kth_ancestor(u, k):
        for j in range(LOG-1, -1, -1):
            if k >= (1 << j):
                u = up[u][j]
                k -= (1 << j)
        return u

    # 读取查询数量 m
    m = int(data[ptr])
    ptr += 1

    # 处理 m 组查询
    res = []
    for _ in range(m):
        p = int(data[ptr])
        q = int(data[ptr+1])
        v1 = int(data[ptr+2])
        v2 = int(data[ptr+3])
        ptr += 4

        r = lca(p, q)
        L = (depth[p] - depth[r]) + (depth[q] - depth[r])
        days = L // (v1 + v2)
        s = v1 * days

        # 找相遇点
        if s <= depth[p] - depth[r]:
            meet = kth_ancestor(p, s)
        else:
            s2 = L - s
            meet = kth_ancestor(q, s2)

        res.append(f"{days} {depth[meet]}")
    
    print('\n'.join(res))

if __name__ == "__main__":
    main()

倍增法（Binary Lifting）
倍增法 是处理树上问题（尤其是 LCA 最近公共祖先 和 第 $k$ 个祖先）最常用的算法之一。
它的核心思想是：与其一步一步往上跳，不如按 2 的幂次（1, 2, 4, 8...）往上跳。
1. 核心思想：二进制拆分
任何正整数都可以表示为 2 的幂次之和。例如：如果要向上跳 $13$ 层，因为 $13 = 8 + 4 + 1$ ( $1101_{2}$ )，我们可以：
先向上跳 $2^{3} = 8$ 层。
再向上跳 $2^{2} = 4$ 层。
最后向上跳 $2^{0} = 1$ 层。
这样，原本需要 13 次的操作，现在只需要 3 次。
2. 预处理：up[u][i] 数组
我们定义 up[u][i] 表示：节点 $u$ 的第 $2^{i}$ 个祖先是谁。
基本情况：up[u][0] 是 $u$ 的直接父节点（跳了 $2^{0} = 1$ 层）。
递推关系：跳 $2^{i}$ 层等于“先跳 $2^{i - 1}$ 层，再跳 $2^{i - 1}$ 层”。
$up [u] [i] = up [up [u] [i - 1]] [i - 1]$
代码实现：
python
# LOG 通常取 18 或 19 (因为 2^18 > 200,000)
for i in range(1, LOG):
    for u in range(1, n + 1):
        # 如果 u 的 2^(i-1) 辈祖先存在，才能找 2^i 辈
        if up[u][i-1] != 0:
            up[u][i] = up[up[u][i-1]][i-1]
3. 应用一：求第 $k$ 个祖先（get_kth_ancestor）
给定节点 $u$ 和步数 $k$ ，如何快速找到它上面的节点？我们检查 $k$ 的二进制表示。如果第 $i$ 位是 1，就往上跳 $2^{i}$ 步。
代码实现：
python
def get_kth_ancestor(u, k):
    for i in range(LOG):
        if (k >> i) & 1: # 如果 k 的二进制第 i 位是 1
            u = up[u][i]
    return u
时间复杂度： $O (\log k)$
4. 应用二：求最近公共祖先（LCA）
求 $u$ 和 $v$ 的 LCA 分为两步：
对齐深度：假设 $u$ 更深，先让 $u$ 向上跳，跳到和 $v$ 同一高度。
一起向上跳：
如果此时 $u == v$ ，说明原先的 $v$ 就是 $u$ 的祖先，LCA 就是 $v$ 。
否则，从大到小尝试跳跃步数 $2^{i}$ 。
关键判断：如果 up[u][i] != up[v][i]，说明跳了 $2^{i}$ 步还没跳过头（还没到公共祖先或者正好在公共祖先下方），那就跳上去。
循环结束后，它们都恰好停在 LCA 的直接子节点上。此时 up[u][0] 就是 LCA。
代码实现：
python
def get_lca(u, v):
    if depth[u] < depth[v]: u, v = v, u
    
    # 1. 提升 u 到和 v 同样深度
    u = get_kth_ancestor(u, depth[u] - depth[v])
    
    if u == v: return u
    
    # 2. 从大步到小步尝试
    for i in range(LOG - 1, -1, -1):
        if up[u][i] != up[v][i]:
            u = up[u][i]
            v = up[v][i]
            
    # 最终停在 LCA 的下一层，返回父节点
    return up[u][0]
时间复杂度： $O (\log n)$
5. 为什么地铁换乘题要用倍增法？
在地铁换乘这道题中，我们需要解决两个核心问题：
算距离： $L = d e p t h (p) + d e p t h (q) - 2 \times d e p t h (L C A (p, q))$ 。
这里必须用倍增法在 $O (\log n)$ 内算出 LCA。
找节点：相遇天数 $T$ 算出后，我们需要知道从 $p$ 出发走 $d_{1} = v_{1} \times T$ 步到达的节点编号。
这正是“求第 $k$ 个祖先”的问题，倍增法可以在 $O (\log n)$ 内完成。
总结
操作暴力法 (一步步爬) 倍增法
预处理 $O (N)$ (只需存父节点) $O (N \log N)$ (存二维表)
求 $k$ 级祖先 $O (k)$ $O (\log k)$
求 LCA $O (N)$ $O (\log N)$
空间换时间：倍增法通过存储额外的 up[u][i] 信息，将查询的时间复杂度从线性降低到了对数级，在 $N = 200, 000$ 的数据规模下是必须的。
具体实例
我们用一个具体的例子来拆解：“如何快速找到一个人的第 6 代祖先？”
1. 场景设定
假设有一条家谱链： 节点 7 → 6 → 5 → 4 → 3 → 2 → 1 → 0 (祖先)
我们要找 节点 7 的第 6 代祖先（也就是节点 1）。
2. 预处理：存下“2的幂次方”步的祖先
在倍增法中，我们不存所有的祖先，只存第 1, 2, 4, 8... 代祖先。
对于 节点 7：
跳 $2^{0} = 1$ 步：是 6 （up[7][0] = 6）
跳 $2^{1} = 2$ 步：是 5 （up[7][1] = 5）—— 其实就是从 6 再跳 1 步
跳 $2^{2} = 4$ 步：是 3 （up[7][2] = 3）—— 其实就是从 5 再跳 2 步
全表的 up 数组看起来像这样（部分）：
节点跳1步( $2^{0}$ ) 跳2步( $2^{1}$ ) 跳4步( $2^{2}$ )
7 6 5 3
6 5 4 2
5 4 3 1
3 2 1 (越界)
3. 实战：寻找节点 7 的第 6 代祖先
关键在于： $6 = 4 + 2$ (二进制是 110)。
第一步：先跳 4 步 ( $2^{2}$ )
我们看 up[7][2]，直接定位到 节点 3。
剩余步数： $6 - 4 = 2$ 步。
第二步：从节点 3 再跳 2 步 ( $2^{1}$ )
我们看 up[3][1]，直接定位到 节点 1。
剩余步数： $2 - 2 = 0$ 步。
结果：找到了！是 节点 1。
为什么快？ 暴力法：7→6→5→4→3→2→1（数了 6 次）倍增法：7→3→1（数了 2 次）
4. 寻找 LCA（最近公共祖先）的逻辑
假设我们要找 节点 7 和 节点 5 的 LCA（在这个例子里显然是 5）。
对齐高度：
节点 7 深度是 7，节点 5 深度是 5。
高度差是 2。
让 7 向上跳 $2^{1} = 2$ 步，查表 up[7][1] 得到 节点 5。
检查是否重合：
现在两个节点都在位置 5，重合了！
LCA 就是节点 5。
5. 为什么要“从大到小”跳？
如果两个节点没重合，我们要一起往上跳，但不能跳过头。
比如我们要找两个人在很远上方的汇合点：
先尝试跳 1024 步。跳过头了（变成同一个祖先了）？不跳。
再尝试跳 512 步。没过头（还是不同的祖先）？跳上去！
再尝试跳 256 步...
这就像用不同长度的尺子（1m, 0.5m, 0.25m...）去凑一段长度。你总是先用最长的尺子去量，量不下了再换短的。
总结
倍增：就是把要跳的距离 $K$ 分解成二进制（如 $13 = 8 + 4 + 1$ ）。
优势：在 20 万个节点的树上，最长路径可能有 20 万。
暴力法：最坏要走 200,000 步。
倍增法：最坏只需跳 $\log_{2} (200, 000) \approx$ 18 步。
这就是为什么 LOG 在代码里通常设为 18 或 19 的原因。
Q：这个二进制拆分，与树状数组的前缀和分组类似
你的直觉非常敏锐！倍增法和树状数组（BIT）在本质逻辑上确实是高度一致的。
它们的核心思想都是：利用数字的二进制拆分（Binary Decomposition），将线性（ $O (N)$ ）的累积过程，转化为对数级（ $O (\log N)$ ）的跳跃过程。
我们可以从以下三个维度来对比这两者的“异曲同工之妙”：
1. 步长的拆分逻辑
树状数组：当你求 prefixSum(13) 时，13 的二进制是 1101（ $8 + 4 + 1$ ）。树状数组会将区间 $[1, 13]$ 拆分为长度为 8、4、1 的三个预先计算好的小段。
倍增法：当你求 getKthAncestor(u, 13) 时，同样将距离 13 拆分为跳 $2^{3} = 8$ 步、再跳 $2^{2} = 4$ 步、最后跳 $2^{0} = 1$ 步。
结论：两者都利用了“任何整数都可以表示为唯一的 2 的幂次之和”这一数学特性。
2. 预处理的“嵌套”关系
这两者都有一个“从小到大、逐层叠加”的构造过程：
倍增法：up[u][i] = up[ up[u][i-1] ][ i-1 ]
要跳 8 步，就是先跳 4 步，再从那儿跳 4 步。
树状数组：tree[x] 存储的是长度为 lowbit(x) 的一段和。
虽然存储形式不同，但它在更新（update）时也是不断通过 i += lowbit(i) 向上层传递信息。
3. 应用场景的平移（线性 vs 树状）
你可以把这两者看作是同一个思想在不同拓扑结构上的应用：
特性树状数组 (BIT) 倍增法 (Binary Lifting)
作用对象 线性序列 (数组) 树形结构 (Tree)
处理内容 区间和、前缀和祖先节点、路径信息
跳跃方向 索引下标的二进制位树的深度/高度
关联算法 类似 Sparse Table (ST表) 它是 ST 表在树上的演变
深度理解：ST 表（Sparse Table）
其实，在“线性序列”和“树”之间，还有一个中间地带，叫 ST 表。
ST 表：用于解决 RMQ（区间最值）问题。它定义的 st[i][j] 表示从下标 $i$ 开始，长度为 $2^{j}$ 的区间内的最大值。
倍增法：其实就是把 ST 表搬到了树上。up[u][i] 就是从节点 $u$ 开始，向上长度为 $2^{i}$ 的“区间”终点。
总结
倍增法本质上就是在树上维护了一个类似于树状数组或 ST 表的二进制跳跃表。
这种“二进制化”的处理方式，是计算机科学中处理结合律运算（加法、取最值、函数复合/跳跃）从 $O (N)$ 优化到 $O (\log N)$ 的最通用、最强大的武器。

T30830: 地铁换乘（多组查询版） ​

T30830: 地铁换乘（多组查询版）