How far away ？ HDU - 2586 trajan算法lca

题意：树上查询两个点之间的距离

题解：必须离线，res[i]=d[u]+d[v]-2*d[lca(u,v)]；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+10, INF = 0x3f3f3f3f;
#define mod 998244353
#define pi acos(-1.0)
int n,m,cnt1,cnt2;
int head1[maxn],head2[maxn];
int vis[maxn];ll d[maxn],res[maxn];
int fa[maxn];
struct node {
    int w,e,next;
    int lca;
}edge[maxn*2],que[maxn*2];

void add(int u,int v,int w){
    edge[cnt1].w=w;
    edge[cnt1].e=v;
    edge[cnt1].next=head1[u];
    head1[u]=cnt1++;
}
void add(int u,int v){
    que[cnt2].e=v;
    que[cnt2].next=head2[u];
    head2[u]=cnt2++;
}

void init(){
    memset(head1,0,sizeof(head1));
    memset(head2,0,sizeof(head2));
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    for(int i=0;i<=n;i++)fa[i]=i;
    cnt1=1;cnt2=1;
}

int Find(int x){
    return fa[x]==x?x:fa[x]=Find(fa[x]);
}

void dfs(int u,int fa,ll w){
    d[u]=w;
    for(int i=head1[u];i!=0;i=edge[i].next){
        int v=edge[i].e;
        if(v==fa)continue;
        dfs(v,u,w+edge[i].w);
    }
}
void lca(int u){ //离线LCA算法
    fa[u]=u, vis[u]=true;
    for(int i=head1[u];i!=0;i=edge[i].next){
        if(!vis[edge[i].e]){
            lca(edge[i].e);
            fa[edge[i].e]=u;
        }
    }
    for(int i=head2[u];i!=0;i=que[i].next){
        if(vis[que[i].e]){
            que[i].lca=Find(que[i].e);
            res[i]=d[u]+d[que[i].e]-2*d[que[i].lca]; //两者距离
        }
    }
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        init();
        for(int i=0;i<n-1;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        dfs(1,-1,0);
        lca(1);
        for(int i=1;i<=m;i++){
            cout<<res[i]<<endl;
        }
    }
}