题意

　　给出一棵树，以及每条边的权值，给出一些询问，每个询问是2个节点，求每个询问对应的2个节点的距离。

算法

　　

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=40000+5;struct Edge{    int cnt,x[N],y[N],z[N],nxt[N],fst[N];    void set(){        cnt=0;        memset(x,0,sizeof x);        memset(y,0,sizeof y);        memset(z,0,sizeof z);        memset(nxt,0,sizeof nxt);        memset(fst,0,sizeof fst);    }    void add(int a,int b,int c){        x[++cnt]=a;        y[cnt]=b;        z[cnt]=c;        nxt[cnt]=fst[a];        fst[a]=cnt;    }}e,q;int T,n,m,from,to,dist,in[N],rt,dis[N],fa[N],ans[N];bool vis[N];void dfs(int rt){    for (int i=e.fst[rt];i;i=e.nxt[i]){        dis[e.y[i]]=dis[rt]+e.z[i];        dfs(e.y[i]);    }}int getf(int k){    return fa[k]==k?k:fa[k]=getf(fa[k]);}void LCA(int rt){    for (int i=e.fst[rt];i;i=e.nxt[i]){        LCA(e.y[i]);        fa[getf(e.y[i])]=rt;    }    vis[rt]=1;    for (int i=q.fst[rt];i;i=q.nxt[i])        if (vis[q.y[i]]&&!ans[q.z[i]])            ans[q.z[i]]=dis[q.y[i]]+dis[rt]-2*dis[getf(q.y[i])];}int main(){    scanf("%d",&T);    while (T--){        q.set(),e.set();        memset(in,0,sizeof in);        memset(vis,0,sizeof vis);        memset(ans,0,sizeof ans);        scanf("%d%d",&n,&m);        for (int i=1;i