Tanjar+并查集（离线查询）

参考博客：https://www.cnblogs.com/jsawz/p/6723221.html

#include<cstdio>
#define N 420000
struct hehe{
    int next;
    int to;
    int lca;
};
hehe edge[N];//树的链表
hehe qedge[N];//需要查询LCA的两节点的链表
int n,m,p,x,y;
int num_edge,num_qedge,head[N],qhead[N];
int father[N];
int visit[N];//判断是否被找过 
void add_edge(int from,int to){//建立树的链表 
    edge[++num_edge].next=head[from];
    edge[num_edge].to=to;
    head[from]=num_edge;
}
void add_qedge(int from,int to){//建立需要查询LCA的两节点的链表 
    qedge[++num_qedge].next=qhead[from];
    qedge[num_qedge].to=to;
    qhead[from]=num_qedge;
}
int find(int z){//找爹函数 
    if(father[z]!=z)
        father[z]=find(father[z]);
    return father[z];
}
int dfs(int x){//把整棵树的一部分看作以节点x为根节点的小树 
    father[x]=x;//由于节点x被看作是根节点，所以把x的father设为它自己 
    visit[x]=1;//标记为已被搜索过 
    for(int k=head[x];k;k=edge[k].next)//遍历所有与x相连的节点 
        if(!visit[edge[k].to]){//若未被搜索 
            dfs(edge[k].to);//以该节点为根节点搞小树 
            father[edge[k].to]=x;//把x的孩子节点的father重新设为x 
        }
    for(int k=qhead[x];k;k=qedge[k].next)//搜索包含节点x的所有询问 
        if(visit[qedge[k].to]){//如果另一节点已被搜索过 
            qedge[k].lca=find(qedge[k].to);//把另一节点的祖先设为这两个节点的最近公共祖先 
            if(k%2)//由于将每一组查询变为两组，所以2n-1和2n的结果是一样的 
                qedge[k+1].lca=qedge[k].lca;
            else
                qedge[k-1].lca=qedge[k].lca;
        }
}
int main(){
    scanf("%d%d%d",&n,&m,&p);//输入节点数，查询数和根节点 
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);//输入每条边 
        add_edge(x,y);
        add_edge(y,x);
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);//输入每次查询，考虑(u,v)时若查找到u但v未被查找，所以将(u,v)(v,u)全部记录 
        add_qedge(x,y);
        add_qedge(y,x);
    }
    dfs(p);//进入以p为根节点的树的深搜 
    for(int i=1;i<=m;i++)
        printf("%d ",qedge[i*2].lca);//两者结果一样，只输出一组即可 
    return 0;
}

倍增LCA（在线查询）

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>
#define MT(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const double E=2.718281828459;
const ll mod=1e12;
const int INF=0x3f3f3f3f;

int t,n,q;

struct node
{
    int e;
    int c;
    int p;
}load[80000];
int head[40005],sign;

void add_edge(int s,int e,int c)
{
    load[++sign]=node{e,c,head[s]};
    head[s]=sign;
}

int grand[40005][18];
int depth[40005];
int dis[40005];
int N;

void dfs(int s,int pre)
{
    for(int i=1;i<=N;i++)
        grand[s][i]=grand[grand[s][i-1]][i-1];
    for(int i=head[s];i!=-1;i=load[i].p)
    {
        int e=load[i].e;
        int c=load[i].c;
        if(e!=pre)
        {
            depth[e]=depth[s]+1;
            grand[e][0]=s;
            dis[e]=dis[s]+c;
            dfs(e,s);
        }
    }
}


void init()
{
    N=log2(n);
    memset(grand,0,sizeof(grand));
    for(int i=1;i<=n;i++)
    {
        head[i]=-1;
        dis[i]=0;
        depth[i]=-1;
    }
    depth[1]=0;
    sign=0;
}

int get_lca(int a,int b)
{
    if(depth[a]>depth[b])
        swap(a,b);
    for(int i=N;i>=0;i--)
    {
        if(depth[b]>=depth[a]&&depth[grand[b][i]]>=depth[a])
            b=grand[b][i];
    }
    for(int i=N;i>=0;i--)
    {
        if(grand[a][i]!=grand[b][i])
        {
            a=grand[a][i];
            b=grand[b][i];
        }
    }
    return a==b?a:grand[b][0];
}

int main()
{
    int s,e,c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&q);
        init();
        for(int i=1;i<n;i++)
        {
            scanf("%d %d %d",&s,&e,&c);
            add_edge(s,e,c);
            add_edge(e,s,c);
        }
        dfs(1,-1);
        while(q--)
        {
            scanf("%d %d",&s,&e);
            int x=get_lca(s,e);
            printf("%d\n",dis[s]+dis[e]-2*dis[x]);
        }
    }
    return 0;
}