十万级节点无向无权树中多节点对路径高效求解方案问询

嘿，针对你这个10万节点规模的树结构路径查询需求，我强烈推荐**倍增法（Binary Lifting）+ 最近公共祖先（LCA）**的组合方案——这可是当前处理大规模树多组路径查询最高效的玩法之一，完美适配你的场景。

树里任意两个节点u和v的唯一路径，本质上就是「u到它们的最近公共祖先（LCA）的路径」加上「v到该LCA的路径」（注意去掉重复的LCA节点）。所以整个问题可以拆成两步：快速找到任意两点的LCA，再基于LCA还原完整路径。

一、预处理阶段（O(n log n) 时间复杂度） #

因为你的树有10万节点，这个预处理的时间和空间成本完全可控。我们需要提前计算两个关键数据：

• depth数组：记录每个节点到根节点的深度（距离）
• 倍增表（up数组）：up[k][u]表示节点u向上跳2^k步到达的节点，k的最大值取log2(n)即可（比如10万的话，log₂(1e5)≈17，所以k到17就足够）

预处理步骤：

1. 选一个根节点（比如节点1），通过一次DFS或BFS遍历整棵树，计算每个节点的depth值，以及up[0][u]（也就是节点u的直接父节点）
2. 用动态规划填充倍增表：对每个k从1到max_level，遍历所有节点u，执行up[k][u] = up[k-1][up[k-1][u]]

二、查询LCA（O(log n) 每组查询） #

给定两个节点u和v，找它们的LCA步骤如下：

1. 先把u和v调整到同一深度：如果depth[u] > depth[v]，就让u通过倍增法快速向上跳depth[u]-depth[v]步（把差值拆成二进制，对应不同的k值来跳）
2. 如果此时u == v，那这个节点就是LCA
3. 否则，从最大的k值往下遍历，如果up[k][u] != up[k][v]，就把u和v同时向上跳2^k步
4. 最后，u的直接父节点（up[0][u]）就是两者的LCA

三、还原完整路径（O(len(path)) 每组查询） #

拿到LCA后，就能轻松还原u到v的路径：

1. 收集u到LCA的路径：从u开始，一步步向上跳到LCA，把经过的节点加入列表（顺序是u→父节点→…→LCA）
2. 收集v到LCA的路径：从v开始向上跳到LCA，把列表反转（原本是v→父节点→…→LCA，反转后变成LCA→…→父节点→v），然后去掉重复的LCA节点，和第一步的列表拼接
3. 最终拼接后的列表就是u到v的完整路径

• 预处理仅需一次，O(n log n)的时间对10万节点完全友好；内存上倍增表是1e5×17≈1.7e6个元素，占用极小
• 每组查询的时间是O(log n + len(path))：log n是找LCA的耗时，len(path)是路径长度（这部分无法避免，毕竟你需要输出路径本身）
• 对比其他方法：暴力DFS/BFS每次查询O(n)，完全扛不住10万节点的多查询；Tarjan离线LCA适合一次性处理所有查询，但如果是在线查询场景，倍增法的灵活性更高

# 初始化全局变量
max_level = 17  # 对应log2(1e5)的上取整
adj = [[] for _ in range(n+1)]  # 邻接表存储树
depth = [0]*(n+1)
up = [[0]*(n+1) for _ in range(max_level)]

# DFS预处理depth和up表
def dfs(u, parent_node):
    depth[u] = depth[parent_node] + 1
    up[0][u] = parent_node
    for k in range(1, max_level):
        up[k][u] = up[k-1][up[k-1][u]]
    for v in adj[u]:
        if v != parent_node:
            dfs(v, u)

# 查找LCA
def find_lca(u, v):
    if depth[u] < depth[v]:
        u, v = v, u
    # 把u跳到和v同一深度
    for k in range(max_level-1, -1, -1):
        if depth[u] - (1 << k) >= depth[v]:
            u = up[k][u]
    if u == v:
        return u
    # 同时向上跳，直到找到LCA
    for k in range(max_level-1, -1, -1):
        if up[k][u] != up[k][v]:
            u = up[k][u]
            v = up[k][v]
    return up[0][u]

# 还原u到v的路径
def get_path(u, v):
    ancestor = find_lca(u, v)
    path_u = []
    # 收集u到LCA的路径
    while u != ancestor:
        path_u.append(u)
        u = up[0][u]
    path_u.append(ancestor)
    # 收集v到LCA的路径并反转
    path_v = []
    while v != ancestor:
        path_v.append(v)
        v = up[0][v]
    # 拼接路径
    return path_u + path_v[::-1]

小提示：实际实现时，可根据编程语言调整细节，比如C++用vector的vector存储倍增表，Python用列表嵌套即可；max_level也可以通过floor(log2(n)) + 1动态计算，更灵活。

内容的提问来源于stack exchange，提问作者chanakya sunkarapally