给定一棵 n 个点的树，Q 个询问，每次询问点 x 到点 y 两点之间的距离。

第一行一个正整数 n，表示这棵树有 n 个节点；

接下来 n−1 行，每行两个整数 x,y表示 x,y 之间有一条连边；

然后一个整数 Q，表示有 Q 个询问；

接下来 Q 行每行两个整数 x,y 表示询问 x 到 y 的距离。

输出 Q 行，每行表示每个询问的答案。

6
1 2
1 3
2 4
2 5
3 6
2
2 6
5 6

3
4

数据范围与提示：

对于全部数据，1≤n≤10^5,1≤x,y≤n

在树论算法中，求解树上任意两点之间的距离是一个极其经典且高频的考点。本题是最近公共祖先（LCA）算法的标准试金石。本文将从零开始，深度剖析如何通过两种截然不同的降维打击手段——“倍增法”与“欧拉序+RMQ”，来解决这一问题。

一、 题目分析

题目核心： 给定一棵包含 N 个节点的无根树（N≤10^5），以及 Q 次查询（Q 的数量级通常与 N 相当或更大）。每次查询要求输出给定的两点 X 和 Y 之间的最短路径距离。

数学转换： 在树形结构中，任意两点 X 和 Y 之间的唯一简单路径，必然会经过它们的最近公共祖先（LCA）。 设 depth[i] 为节点 i 到根节点的深度（距离），那么 X 到 Y 的距离公式可以完美转化为： Distance(X,Y)=depth[X]+depth[Y]−2×depth[LCA(X,Y)]

因此，本题的终极目标被简化为：如何在面对海量查询时，极速求出 LCA(X,Y)。

二、 算法一：倍增法

1. 解题思路与思考过程

如果采用暴力做法，让 X 和 Y 一步一步往上爬，最坏情况（树退化成链）单次查询的时间复杂度会达到 O(N)，面对 Q 次查询必定超时。 为了加速爬树过程，我们可以利用二进制拆分的思想。任何一个数字都可以表示为若干个 2 的幂次方之和。既然每次只能跳 1 步太慢，我们能否预处理出每个节点往上跳 1,2,4,8…2^j 步会到达哪里？这就是倍增法的核心。

2. 算法设计

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

• 状态转移： 跳 2^j 步，等价于先跳 2^(j−1) 步到达一个“中转站”，然后再从“中转站”跳 2^(j−1) 步。即：fa[i][j] = fa[fa[i][j-1]][j-1]。

• 预处理（DFS）： 选定 1 号节点为根，从上往下遍历，在到达每个节点时，利用已经算好的祖先信息，动态规划填满该节点的 fa 数组。

• 查询 LCA（三步走）：

  1. 齐平水位线： 将深度较大的节点，利用二进制拆分向上跳，直到与另一个节点深度相同。

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

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

3. 代码实现与详细注释

//这道题求出lca(x,y)之后就很容易求出x和y两点之间的距离了

//第一种方法倍增求lca
//1.用邻接表把边的关系存起来
//2.因为是树 所以选择任意一个点作为根节点
//3.对邻接表走一遍dfs 得到依赖关系（树）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> vec[100010];//邻接表存图
int n,q;
int depth[100010];//存储每个节点的深度 假定根节点深度为1
int fa[100010][20];//fa[i][j]表示节点i向上跳2^j步所表示的祖先

//dfs预处理深度和倍增fa数组
//rt为当前节点 p为rt的父节点 
void dfs(int rt,int p){
    //当前节点向上一步是自己的父节点
    fa[rt][0]=p;
    //子节点的深度为父节点+1
    depth[rt]=depth[p]+1;
    
    //接下来dp处理倍增数组信息
    //限制条件(1<<i)<=depth[rt] 防止跳跃距离超过当前深度
    for(int i=1;(1<<i)<=depth[rt];i++){
        fa[rt][i]=fa[fa[rt][i-1]][i-1];
    }

    //遍历rt的每个孩子
    for(int i:vec[rt]){
        //避免重复访问 如果访问到父节点就跳过
        if(i==p) continue;
        dfs(i,rt);
    }
}

//查询x和y的最近公共祖先
int lca(int x,int y){
    //1.让x永远是x和y中深度较大的那一个 方便后续操作
    if(depth[x]<depth[y]) swap(x,y);

    //2.让x和y去到同一层（深度相同）
    while(depth[x]!=depth[y]){
        //让x向上跳 直到和y同一深度
        //利用__lg找到能跳的最大2的次幂
        x=fa[x][__lg(depth[x]-depth[y])];
    }

    //3.如果x和y在同一深度后 x等于y 说明y就是lca(x,y)的最近公共祖先
    if(x==y) return y;

    //4.如果x和y在同一深度后 x不等于y
    //就让x和y一起往上跳 如果跳到同一个点 就缩小跳的步数重新跳
    //从而不断逼近lca(x,y)的正下方
    //最大可能跳跃高度不会超过当前节点的深度
    //所以从 __lg(depth[x])开始倒序遍历
    for(int i=__lg(depth[x]);i>=0;i--){
        //只要没有跳到同一个点就可以跳
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    //最后x和y一定是在lca(x,y)的正下方
    //返回x的父节点（x和y的最近公共祖先）
    return fa[x][0];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        //无向边双向存边
        vec[x].push_back(y);
        vec[y].push_back(x);
    }

    //1.假定1号节点为根节点，走一号节点开始一圈dfs 建树 
    //得到父节点和深度信息 以及倍增数组信息
    depth[1]=1;//预设根节点深度为1
    //根节点没有父节点 设置为0
    dfs(1,0);

    //2.接下来就是查询最近公共祖先
    cin>>q;//询问次数
    while(q--){
        int x,y;
        cin>>x>>y;
        //x到y的距离就=x到lca(x,y)的距离+y到lca(x,y)的距离
        cout<<depth[x]+depth[y]-2*depth[lca(x,y)]<<"\n";
    }
    return 0;
}

三、 算法二：欧拉环游（欧拉序）+RMQ

1. 解题思路与思考过程

倍增法虽然优秀，但单次查询时间为 O(logN)。如果查询次数 Q 达到百万级别，依然有超时的风险。此时，我们需要彻底改变数据结构，将树形图降维成一维数组，将 LCA 问题转化为经典的 RMQ（区间最值查询） 问题。

2. 算法设计

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

• 核心数学性质： 节点 X 和 Y 在欧拉序 E 表中会有多次记录。找到它们第一次出现的位置（记为 H[X] 和 H[Y]）。在欧拉序的区间 [H[X],H[Y]] 之间，深度最浅（即 L 表中值最小）的那个节点，必定是 X 和 Y 的最近公共祖先。

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

3. 代码实现与详细注释

//第二种方法rmq求lca
#include <iostream>
#include <algorithm>//对应swap
#include <vector>
using namespace std;
int n,q;
//邻接表
vector<int> vec[100010];//邻接表

//存储从下标i开始 长度为2^j的区间内 深度最小的节点的下标
int st[200020][25];

//表e是对树进行欧拉环游过程中所有访问到的节点
//e[i]是在环游过程中第i个访问的节点
int e[200020];

//表l是在欧拉环游过程中访问到的节点所处的层数
//l[i]是e[i]所对应的层数（深度）
int l[200020];

int h[100010];//h[i]代表在e表中i第一次出现的位置（下标）

int cnt=0;//欧拉序计数器


//rt为当前节点 fa为当前节点的父节点
void dfs(int rt,int fa){
    //记录当前访问节点
    e[++cnt]=rt;
    //该节点深度为上一个节点+1
    l[cnt]=l[cnt-1]+1;
    //记录rt节点第一次在e表中出现的位置
    h[rt]=cnt;

    //遍历当前节点的所有邻接点
    for(int v:vec[rt]){
        //避免重复访问
        if(v==fa) continue;
        dfs(v,rt);
        //回溯
        e[++cnt]=rt;
        //回溯是往回走 所以深度要减1
        l[cnt]=l[cnt-1]-1;
    }
}

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

    //外层循环遍历区间长度的指数
    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];
        }
    }
}

//查询区间[x,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;
    //邻接表存图
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        //无向边双向加边
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    //dfs遍历预处理生成表e 表l 表h
    //因为是树 所以任意节点都可以假定为根节点 假设1号点为根节点
    //根节点不存在父节点 传个0
    dfs(1,0);

    //接下来预处理生成关于l的st表
    pre();
    cin>>q;
    //总共q次询问
    while(q--){
        int x,y;
        cin>>x>>y;
        //x到y的距离=x到lca(x,y)的距离+y到lca(x,y)的距离
        //要找到x y第一次在e表中出现的位置h[x] h[y]
        //然后代入到l中去找中间深度最小的点
        cout<<l[h[x]]+l[h[y]]-2*l[query(h[x],h[y])]<<"\n";
    }
    return 0;
}

四、 时空复杂度分析

对比维度	倍增法	RMQ (欧拉序+ST表)
空间复杂度	O(NlogN) (维护fa数组)	O(NlogN) (维护ST表，第一维度需开到2*N)
预处理时间	O(NlogN) (DFS附带状态转移)	O(NlogN) (DFS+ST表构建)
单次查询时间	O(logN) (向上跳跃)	O(1) (极速查询)
总时间复杂度	O((N+Q)logN)	O(NlogN+Q)

实战指南： 倍增法逻辑极其直观，代码简洁，且非常容易扩展（例如在树上维护路径最大值、求边权等），是 90% 考场环境下的首选。RMQ 算法则是为了应对极致查询量（Q 远大于 N）而生的终极优化方案，纯粹为追求 O(1) 查询速度而存在。

五、 坑点总结

1. __lg(0) 的未定义行为（致命Bug）： 在使用 GCC 内置的高效寻位函数 __lg() 时，务必保证传入的参数严格大于 0。如果在倍增法中，两点深度已经齐平，再次使用 __lg(depth[x]-depth[y]) 会导致程序崩溃。

2. 欧拉序的数组容量： 欧拉环游会包含所有回溯过程，最终序列长度是 2*N−1。因此，保存欧拉序的 E 表、L 表，以及 ST 表的第一维度，必须开到200000以上，切忌开成N导致越界。

3. ST表“值”与“下标”的剥离混淆： 在构建 ST 表和查询 RMQ 时，一定要时刻清醒：我们比较的是深度值 l[...]，但 ST 表存储和返回的是欧拉序的下标。一旦混淆，必然引发段错误。

4. 编译依赖： 代码中大量运用了swap与 __lg函数，必须显式包含 <algorithm> 头文件，防止在严苛的评测机上引发编译错误。