算法1

(倍增LCA) $O((n+m)logn)$

对于每一次询问，都再去算一遍，相当于在线做法

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=10010,M=20010;

int h[N],e[M],ne[M],w[M],idx;
int depth[N],fa[N][16],q[N];
int n,m,dist[N];

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}

void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;//0点作用有许多,如果某个点跳出去那他的祖宗点就是0,而且
    //跳出去以后深度为0,便不会执行跳的操作,节省了很多代码！
    int tt=0,hh=0;
    q[tt++]=root;
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q[tt++]=j;
                if(tt==N) tt=0;
                fa[j][0]=t;
                for(int k=1;k<=15;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];//跳出去也不要紧,变成0而已！
            }
        }
    }
}

int query(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);//把2个放到同一层,只对深度高的那个进行操作
    for(int k=15;k>=0;k--)//二进制拼凑实行跳
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    if(a==b) return a;
    for(int k=15;k>=0;k--)//跳到同一层后,再同时往上跳,直到祖宗节点的下一个,便于判断！
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    return fa[a][0];//最终返回a的父节点或者b的即可
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
       int a,b,c;
       scanf("%d%d%d",&a,&b,&c);
       add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);
    bfs(1);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a==b) printf("0\n");
        else
        {
            int p=query(a,b);
            int res=dist[a]+dist[b]-dist[p]*2;
            printf("%d\n",res);
        }
    }
    return 0;
}

算法2

(tarjan 离线LCA) $O(n+m)$

先将所有的询问都存储下来，最终在tarjan的过程中全部计算

C++ 代码

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int N=10010,M=N*2;

int h[N],e[M],ne[M],w[M],idx;
int res[M],p[N],dist[N];
vector<pair<int,int>> q[N];
int n,m,st[N];

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

void tarjan(int u)
{
    st[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j]=u;
        }
    }
    for(auto x : q[u])
    {
        int y=x.first,id=x.second;
        if(st[y]==2)
        {
            int at=find(y);
            res[id]=dist[y]+dist[u]-dist[at]*2;
        }
    }
    st[u]=2;
}

int main()
{
    cin>>n>>m;
    memset(h,- 1,sizeof h);
    for(int i=1;i<n;i++)
    {
       int a,b,c;
       scanf("%d%d%d",&a,&b,&c);
       add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a!=b)
        {
            q[a].push_back({b,i});
            q[b].push_back({a,i});
        }
    }
    tarjan(1);
    for(int i=0;i<m;i++)  printf("%d\n",res[i]);
    return 0;
}