给出 n 个点的一棵树，多次询问两点之间的最短距离。

注意：边是双向的。

第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；

下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；

再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。

输出 m 行。对于每次询问，输出一行。

2 2 
1 2 100 
1 2 
2 1

100
100

样例输入 2

3 2
1 2 10
3 1 15
1 2
3 2

样例输出 2

10
25

数据范围与提示：

对于全部数据，2≤n≤10^4,1≤m≤2×10^4,0<k≤100,1≤x,y≤n。

在树论算法中，求解树上任意两点之间的距离是一个经典且高频的考点。无论是初学者打基础，还是在正式竞赛中作为复杂题目的一个底层模块，掌握它都至关重要。

本文将从最核心的数学转换入手，深度剖析如何通过两种截然不同的降维打击手段——“倍增法”与“欧拉序 + RMQ”，来解决带权树上的距离查询问题。

一、 题目分析与核心思路

题目核心： 给定一棵包含 n 个节点的无根树（节点间有权值），以及 m 次查询。每次查询要求输出给定的两点 x 和 y 之间的最短路径距离。 数据范围：n≤10^4，m≤2×10^4。

思考过程（数学转换）： 在树形结构中，任意两点 x 和 y 之间的唯一简单路径，必然会经过它们的最近公共祖先（LCA）。 如果在遍历树的时候，我们预处理出每个节点到根节点的物理距离（记为 dis[i]），那么 x 到 y 的距离公式可以完美转化为差分形式：

Distance(x,y)=dis[x]+dis[y]−2×dis[LCA(x,y)]

为什么这个公式成立？ dis[x]+dis[y] 相当于把“从根节点到 x 的路”和“从根节点到 y 的路”加了起来。但是，从“根节点”到“LCA”的这段路径被重复计算了两次。因此，减去 2×dis[LCA] 后，剩下的刚好就是 x 到 y 的真实树上路径长度。

因此，本题的目标被彻底简化为：如何在面对 m 次查询时，极速求出 LCA(x,y)。

二、 算法一：倍增法

1. 算法设计

倍增法的核心思想是二进制拆分。每次往上爬 1 步太慢，我们利用动态规划预处理出每个节点往上跳 1,2,4,8…2^j 步到达的祖先。

• 状态定义： fa[i][j] 表示节点 i 向上跳 2^j 步所到达的祖先节点。

• 状态转移： fa[i][j]=fa[fa[i][j-1]][j-1]。

• 查询 LCA（三步走）：

  1. 齐平水位线： 将深度较大（在下面）的节点，利用 log2​ （代码中使用更快的 __lg 函数）找到最大能跳的 2 的次幂，向上跳跃直到与另一个节点深度相同。

  2. 特判相遇： 如果此时两点重合，说明较浅的点本身就是 LCA。

  3. 同频逼近： 两点同时从最大步数开始试探向上跳。如果跳到的祖先不同，就放心跳上去；如果相同，说明跳过头了或者正好是 LCA，不跳。循环结束后，两人必定停在 LCA 的正下方，再往上走 1 步即为答案。

2. 时空复杂度

• 时间复杂度： * 预处理 DFS：O(nlogn)

  • 单次查询：O(logn)

  • 总时间复杂度：O((n+m)logn)。应对 2×10^4 的数据量绰绰有余。

• 空间复杂度： O(nlogn)，主要消耗在 fa[n][20] 数组上。

三、 算法二：RMQ（欧拉序 + ST表）

1. 算法设计

面对海量查询，倍增的 O(logn) 仍有优化空间。RMQ 算法通过将树形结构降维成一维数组，将 LCA 问题转化为静态区间的最值查询问题，从而实现单次查询 O(1)。

• 欧拉环游（拍扁树）： 沿着树做 DFS，不论是“初次到达”还是“从子树回溯”，只要经过节点就打卡记录。这样会生成一个长度为 2n−1 的节点访问序列（e 表）以及对应的深度序列（l 表）。

• 核心数学性质： 找到 x 和 y 在欧拉序中第一次出现的位置（h[x] 和 h[y]）。在欧拉序的区间 [h[x],h[y]] 之间，深度最浅（即 l 表中值最小）的那个节点，必定是它们的 LCA。

• ST 表提速： 利用ST表算法预处理深度表 l，即可在 O(1) 时间内查询出任意区间内深度最小值的下标，映射回 e 表得出 LCA。

2. 时空复杂度

• 时间复杂度： * 预处理 DFS + ST表构建：O(nlogn)

  • 单次查询：O(1)

  • 总时间复杂度：O(nlogn+m)。查询速度达到理论极限。

• 空间复杂度： O(nlogn)。由于欧拉序长度为 2n，ST 表第一维需开到 2n。

四、 核心坑点总结（避坑指南）

在具体实现这两种算法时，极其容易踩到以下边界陷阱：

1. __lg() 的定义域死穴： __lg(x) 的底层是位扫描指令，传入 0 会导致未定义行为。在倍增法的“齐平水位线”操作时，必须确保是大深度减小深度：__lg(depth[x]-depth[y])，且循环条件严格为 depth[x]!=depth[y]（或 >）。

2. ST表的右边界对齐： 在构建 ST 表时，区间起点为 i，长度为 1<<j，则区间右端点为 i+ (1<<j)-1。必须保证右端点不超过总长度 2n−1。少减 1 会导致末尾合法数据被截断。

3. 欧拉序的数组容量越界： 欧拉环游包含所有回溯过程，最终序列长度是 2n−1。因此，保存欧拉序的 e 表、l 表，以及 ST 表的第一维度、前向星的边数组，必须开到 2×10^4 以上（maxn<<1）。

4. 头文件遗漏： 使用 swap 和 __lg 函数必须显式包含 #include <algorithm>，否则在严格的评测机上直接触发CE。

五、 完整题解代码

版本一：倍增法求 LCA

//x y两点之间的最短距离即为x到lca(x,y)的距离+y到lca(x,y)的距离
//所以两种方法可以求lca 

//第一种方法倍增求lca
#include <iostream>
#include <vector>
#include <cstring>//对应memset
#include <algorithm>//对应swap等函数
using namespace std;
int n,m;
int dis[10010];//dis[i]代表点i到根节点的距离
int depth[10010];//depth[i]代表节点i的深度 根节点深度设置为1
//fa[i][j]代表i节点向上2^j步后所处的节点位置
int fa[10010][20];
int h[10010];//h[u]存储节点u的最后一条边的编号
int vtex[20020];//vtex[i]存储第i条边指向的终点 (无向图开两倍)
int nxt[20020];//nxt[i]存储与第i条边同起点的上一条边的编号
int wt[20020];//wt[i]存储第i条边的权重
int idx;

//链式前向星存图
void addedge(int u,int v,int w){
    vtex[idx]=v;
    nxt[idx]=h[u];
    wt[idx]=w;
    h[u]=idx++;
}

//rt为当前节点 fat为当前节点的父节点 d为父节点到当前节点到距离
void dfs(int rt,int fat,int d){
    dis[rt]=dis[fat]+d;//累加距离
    depth[rt]=depth[fat]+1;//深度=父节点深度+1
    //当前节点向上一步为父节点
    fa[rt][0]=fat;

    for(int i=1;(1<<i)<=depth[rt];i++){
        fa[rt][i]=fa[fa[rt][i-1]][i-1];
    }

    int p=h[rt];//获取当前节点的第一条边
    //遍历当前节点的所有邻接点
    while(p!=-1){
        if(vtex[p]==fat){
            //因为是无向图 如果邻接点是父亲 直接跳过
            p=nxt[p];
            continue;
        }
        dfs(vtex[p],rt,wt[p]);
        p=nxt[p];
    }
}

//查询节点x y的最近公共祖先
int lca(int x,int y){
    //让x是x和y里深度较大的那一个 方便后面计算
    if(depth[x]<depth[y]) swap(x,y);

    //然后让x和y到同一层
    //让x不断向上跳 直到和y处于同一深度
    while(depth[x]!=depth[y]){
        x=fa[x][__lg(depth[x]-depth[y])];
    }
    //如果到同一层后 x等于y 说明y就是x和y的最近公共祖先
    if(x==y) return y;

    //如果不等 就让x和y往上跳 如果跳到同一个点就缩小步数重新跳
    //最后x和y一定是停在他们的最近公共祖先的正下方
    for(int i=__lg(depth[x]);i>=0;i--){
        //如果跳2^i步后 两者的祖先不同 说明还没越过lca
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    //最后停留在x和y的最近公共祖先的正下方
    return fa[x][0];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    //初始化头指针数组为空
    memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++){
        int x,y,k;
        cin>>x>>y>>k;
        //双向存边
        addedge(x,y,k);
        addedge(y,x,k);
    }
    //dfs遍历预处理出fa数组以及depth(深度数组)
    //因为是树 所以任意节点都可以做为根节点 
    //我们假定1号节点为根节点 
    //根节点没有父节点 设置为0
    //根节点到根节点的父节点的距离为0
    dfs(1,0,0);

    //共m次询问
    while(m--){
        int x,y;
        cin>>x>>y;
        //x到y的最短距离就是
        //x到根节点的距离-lca(x,y)到根节点的距离+
        //y到根节点的距离-lca(x,y)到根节点的距离
        cout<<dis[x]+dis[y]-2*dis[lca(x,y)]<<"\n";
    }
    return 0;
}

版本二：RMQ 法（欧拉序 + ST表）求 LCA

//第二种方法RMQ求lca
#include <iostream>
#include <cstring>//对应memset
#include <algorithm>//对应swap
using namespace std;
int n,m;
const int maxn=10010;

//e[i]代表对树进行欧拉环游过程中第i个访问到的节点
int e[maxn<<1];
//l[i]代表欧拉环游过程中所访问到的节点所处的层数
int l[maxn<<1];
int h[maxn];//h[i]代表i节点第一次在e表中出现的位置
int cnt;//欧拉环游过程中总共访问了多少个点

int h2[maxn];
int vtex[maxn<<1];
int nxt[maxn<<1];
int wt[maxn<<1];
int idx;

//d[i]代表i点到根节点的距离
int d[maxn];

//st[i][j]代表以i为起点 区间长度为2^j的区间内 l（深度）最小的下标
int st[maxn<<1][20];

//链式前向星存图
void addedge(int u,int v,int w){
    vtex[idx]=v;
    nxt[idx]=h2[u];
    wt[idx]=w;
    h2[u]=idx++;
}

//欧拉环游 rt为当前节点 fa为当前节点父节点
void dfs(int rt,int fa){
    //记录访问当前节点
    e[++cnt]=rt;
    //当前访问节点为上一个访问节点儿子
    //所以当前访问节点深度为上一个访问节点深度+1
    l[cnt]=l[cnt-1]+1;
    //rt节点第一次在e表中出现的位置下标是cnt
    h[rt]=cnt;

    int p=h2[rt];
    //遍历当前节点的所有邻接点
    while(p!=-1){
        //避免重复访问
        if(vtex[p]==fa){
            p=nxt[p];
            continue;
        }
        //记录节点到根节点的距离
        d[vtex[p]]=d[rt]+wt[p];
        dfs(vtex[p],rt);
        //回溯 再记录一次
        e[++cnt]=rt;
        //回溯 所以当前访问节点是上一个访问节点父亲
        //所以当前访问节点深度是上一个访问节点-1
        l[cnt]=l[cnt-1]-1;
        p=nxt[p];
    }
}

//生成关于l表的st数组
void pre(){
    //以i为起点 区间长度为1的区间内 l最小值的下标就是自己
    for(int i=1;i<=2*n-1;i++) st[i][0]=i;

    //外层循环 遍历区间长度的指数j
    for(int j=1;1<<j<=2*n-1;j++){
        int tmp=1<<(j-1);
        //内层循环 遍历起点 确保右端点不越界
        for(int i=1;i+(1<<j)-1<=2*n-1;i++){
            if(l[st[i][j-1]]<l[st[i+tmp][j-1]])
                st[i][j]=st[i][j-1];
            else
                st[i][j]=st[i+tmp][j-1];
        }
    }
}

//st表查询l[x]和l[y]区间最小值的下标
int query(int x,int y){
    //确保y永远是x y中较大的 方便后面计算
    if(y<x) swap(x,y);
    int k=__lg(y-x+1);
    int tmp=1<<k;
    if(l[st[x][k]]<l[st[y-tmp+1][k]]) return st[x][k];
    else return st[y-tmp+1][k];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    //初始化头指针数组为空
    memset(h2,-1,sizeof(h2));
    //链式前向星存图
    for(int i=1;i<n;i++){
        int x,y,k;
        cin>>x>>y>>k;
        addedge(x,y,k);
        addedge(y,x,k);
    }
    //接下来进行欧拉环游 生成e l h表
    //假设1号节点为根节点 从1号节点开始遍历
    //根节点没有父节点 所以给个虚拟父节点0
    dfs(1,0);
    //预处理完之后 需要对l表进行处理
    //生成关于l表的倍增数组
    pre();
    //m次询问
    while(m--){
        int x,y;
        cin>>x>>y;
        //查询h[x] h[y] 即x和y在e表中第一次出现的位置
        //然后e[h[x]],e[h[y]]之间深度最小的点就是lca(x,y)
        //求出lca(x,y)之后 x到y的最短距离就是
        //x到根节点的距离-lca(x,y)到根节点的距离+
        //y到根节点的距离-lca(x,y)到根节点的距离
        //1.h[x]和h[y]找到两点在欧拉序里的首次出现下标
        //2.query()返回在这个下标区间内找深度最浅的点的下标
        //3.e[]将这个最浅的下标映射回真实的lca节点编号
        cout<<d[x]+d[y]-2*d[e[query(h[x],h[y])]]<<"\n";
    }
}