利用用并查集的高效,与父节点合并
一次性查询O(n+q).
对应模板题hdu2856

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
//#define ll __int64
//#define int ll
typedef  long long ll;
typedef unsigned long long ull;
const int MAXN=4e4+10;
const int MOD=1e9+7;
const double eps=1e-6;
const double finf=1e10;
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
//-------------------------------------------//
struct node
{
    int to,no;
    node(int a=0,int b=0):to(a),no(b){}
};
vector<node> qu[MAXN],g[MAXN];
int vis[MAXN],pre[MAXN],ans[MAXN],dis[MAXN];
int unfind(int x)
{
    return x==pre[x]?x:pre[x]=unfind(pre[x]);
}
void _merge(int a,int b)
{
    int x=unfind(a);
    int y=unfind(b);
    if(a!=b)pre[a]=b;
}
void tarjan(int u)
{
    vis[u]=1;
    for(int i=0;i<g[u].size();++i)
    {
        int v=g[u][i].to,w=g[u][i].no;
        if(vis[v])continue;
        dis[v]=dis[u]+w;
        tarjan(v);
        _merge(v,u);
    }
    for(int i=0;i<qu[u].size();++i)
    {
        node x=qu[u][i];//cout<<u<<endl;
        if(!vis[x.to])continue;
        ans[x.no]=dis[u]+dis[x.to]-2*dis[unfind(x.to)];
    }
}
void init()
{
    memset(vis,0,sizeof vis);
    for(int i=0;i<MAXN;++i)
    {
        pre[i]=i;
        g[i].clear();
        qu[i].clear();
    }
}
int main()
{
    int t;
    read(t);
    while(t--)
    {
        int n,m;
        read(n);read(m);
        init();
        for(int i=0;i<n-1;++i)
        {
            int u,v,w;
            read(u);read(v);read(w);
            g[u].push_back(node(v,w));
            g[v].push_back(node(u,w));
        }
        for(int i=0;i<m;++i)
        {
            int u,v;
            read(u);read(v);
            qu[u].push_back(node(v,i));
            qu[v].push_back(node(u,i));
        }
        tarjan(1);
        for(int i=0;i<m;++i)printf("%d\n",ans[i]);
    }
    return 0;
}

用二进制的思想跳跃式查找
预处理复杂度O(nlogn),单次查询复杂度O(logn).
对应模板题 洛谷P3379

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
//#define ll __int64
//#define int ll
typedef  long long ll;
typedef unsigned long long ull;
const int MAXN=5e5+10;
const int MOD=1e9+7;
const double eps=1e-6;
const double finf=1e10;
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
//-------------------------------------------//
int depth[MAXN],fa[MAXN][20],n,m,s;
vector<int> g[MAXN];
void dfs(int u,int pre,int d)
{
    depth[u]=d;
    fa[u][0]=pre;
    for(int i=0;i<g[u].size();++i)
    {
        int v=g[u][i];
        if(v!=pre)dfs(v,u,d+1);
    }
}
void init()
{
    dfs(s,-1,0);
    for(int i=0;(1<<(i+1))<n;++i)
        for(int j=1;j<=n;++j)
        {
            if(fa[j][i]<0)fa[j][i+1]=-1;
            else fa[j][i+1]=fa[fa[j][i]][i];
        }
}
int LCA(int u,int v)
{
    if(depth[u]>depth[v])swap(u,v);
    int temp=depth[v]-depth[u];
    for(int i=0;(1<<i)<=temp;++i)
        if((1<<i)&temp)v=fa[v][i];
    if(u==v)return u;
    for(int i=(int)log2(n*1.0);i>=0;--i)
    {
        if(fa[u][i]!=fa[v][i])
        {
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
int main()
{
    //freopen("input.txt","r",stdin);
    while(~scanf("%d%d%d",&n,&m,&s))
    {
        for(int i=0;i<=n;++i)g[i].clear();
        for(int i=0;i<n-1;++i)
        {
            int u,v;
            read(u);read(v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        init();
        while(m--)
        {
            int u,v;
            read(u);read(v);
            printf("%d\n",LCA(u,v));
        }
    }
    return 0;
}