一、向上标记法

比如求x，y的lca，我们先从x向上走到根节点，中途标记每个被走过的点，然后从y向上标记，直到遇到第一个被标记的点就是他们的lca了。(不适用于多次查询操作）
时间复杂度：O(n)

二、树上倍增法

这种方法主要是利用了倍增的思想，不断地向上试探，同时利用dp不断转移到上面，然后即可求出lca，

/*
            树上倍增法求最近公共祖先
    时间复杂度： O ((n+m)log(n))
 1、d[x]表示x的深度，不妨设d[x]>=d[y](否则x，y交换）
 2、用二进制拆分的思想，把x向上调整到和y同一深度
 3、若此时x=y，则说明找到了LCA，LCA就是y
 4、用二进制拆分的思想，把x，y同时向上调整，变更且保持两者深度一致且不相会
 5、此时x，y必定只差一步就会相会了，此时他们的父结点f[x,0]就是LCA 
 f[x,k]表示x的2^k辈祖先，即从x向根结点走了2^k步到达的结点 
*/
#include<bits/stdc++.h>
using namespace std;
const int size=50010;
int T,n,m,tot,t;
int f[size][20],d[size],dist[size];
int ver[size*2],nxt[size*2],edge[size*2],head[size*2];
queue<int> q;
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}
void bfs(){  //预处理 
    q.push(1),d[1]=1;
    while(q.size()) {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(d[y]) continue;
            d[y]=d[x]+1;  //y的结点深度加1 
            dist[y]=dist[x]+edge[i];
            f[y][0]=x;
            for(int j=1;j<=t;j++){
                f[y][j]=f[f[y][j-1]][j-1];  //不断更新各祖先 
            }
            q.push(y);
        }
    }
}
int lca(int x,int y){  //计算树上任意两点之间的距离 
    if(d[x]>d[y]) swap(x,y);  //令x的深度小于y的深度，即x更靠经公共祖先 
    for(int i=t;i>=0;i--){
        if(d[f[y][i]]>=d[x])  y=f[y][i];  //y不断向上进行调整 
    }
    if(x==y) return x;
    for(int i=t;i>=0;i--){
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];  //x不算进行向上调整 
    }
    return f[x][0];  //x向上调整1步即可得到lca 
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        t=(int)(log(n)/log(2))+1;
        for(int i=1;i<=n;i++) head[i]=d[i]=0;
        tot=0;
        for(int i=1;i<n;i++){
            int x,y,z;
            cin>>x>>y>>z;
            add(x,y,z);
            add(y,x,z);
        }
        bfs();
        //进行m次查询，查询任意两点之间的距离 
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            cout<<dist[x]+dist[y]-2*dist[lca(x,y)];
        }
    }
    return 0;
}

三、tarjan算法

该算法就是一个对向上标记法的一个优化，采用的是离线查询的操作，先记录下每次询问的操作，然后利用tarjan算法进行一个标记，同时开并查集进行一个优化。

//时间复杂度O(n+m)
#include<bits/stdc++.h> 
using namespace std;
const int size=5010;
int ver[size*2],nxt[size*2],head[size*2],edge[size*2];
int fa[size],d[size],v[size],lca[size],ans[size];
vector<int> query[size],query_id[size];
int T,n,m,tot,t;
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z;
    nxt[tot]=head[x],head[x]=tot;
}
void add_query(int x,int y,int id){  //记录查询情况 
    query[x].push_back(y),query_id[x].push_back(id);
    query[y].push_back(x),query_id[y].push_back(id);
}
int get(int x){  //寻找父结点 
    if(x==fa[x])  return x;
    return fa[x]=get(fa[x]);
}
void tarjan(int x){
    v[x]=1;  //开始递归，但是还没有回溯 
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(v[y])  continue;
        d[y]=d[x]+edge[i];
        tarjan(y);
        fa[y]=x;   //标记父结点 
    }
    for(int i=0;i<query[x].size();i++){  //查询关于x的所有询问 
        int y=query[x][i],id=query_id[x][i];
        if(v[y]==2){  //这个结点是访问完毕并且回溯的结点 
            int lca=get(y);  //直接找到父结点 
            ans[id]=min(ans[id],d[x]+d[y]-2*d[lca]);
        }
    }
    v[x]=2;  //标记这个结点 
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){  //清空 
            head[i]=0,fa[i]=i,v[i]=0;
            query[i].clear(),query_id[i].clear();
        }
        tot=0;
        for(int i=1;i<n;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z),add(y,x,z);
        }
        for(int i=1;i<=m;i++){  //进行m次查询 
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y) ans[i]=0;
            else{
                add_query(x,y,i);
                ans[i]=1<<30;
            }
        }
        tarjan(1);
        for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}