题目链接：

题意：

无向图，给定边及边权重，任意两点之间都有一条唯一的道路，道路上每个点只能出现一次。给定询问，求询问的结点之间的距离。

分析：

路上每个点只能出现一次~可以转化成有根树，问题也即为求最近公共祖先问题~~

这里每条边加上了距离，求出lca后，用u、v的距离根的距离和减去2倍的根到最近公共祖先的距离即可~

代码：

#include
     
      #include
      
       #include
       
        using namespace std;#define mem(a, b) memset(a, b, sizeof(a))#define fuck cout<<"fuck"<
        
         p;vector
         
G[maxn];#define fi first#define se secondint pa[maxn];bool vis[maxn];bool in[maxn];int ance[maxn];int dist[maxn];int n, tot;int head[maxn];int ans[maxn];struct Query{
    int to, next, index;};Query query[maxq * 2];void add_query(int u, int v, int index){    query[tot].to = v;    query[tot].index = index;    query[tot].next = head[u];    head[u] = tot++;    query[tot].to = u;    query[tot].index = index;    query[tot].next = head[v];    head[v] = tot++;}int _find(int x){    if(pa[x] != x) return pa[x] = _find(pa[x]);    return x;}void unite(int x, int y){    int rx = _find(x), ry = _find(y);    if(rx == ry) return;    pa[rx] = ry;}void init(){    tot = 0;   for(int i = 1; i <= n; i++){        G[i].clear();        pa[i] = i;   }    mem(ance, 0);    mem(vis, false);    mem(head, -1);    mem(dist, 0);    mem(in, false);    mem(ans, 0);}void LCA(int u){    ance[u] = u;    vis[u] = true;    for(int i = 0; i < G[u].size(); i++){        int v = G[u][i].fi;        if(vis[v]) continue;        dist[v] = dist[u] + G[u][i].se;        LCA(v);        unite(u, v);        ance[_find(u)] = u;    }    for(int i = head[u]; i != -1; i = query[i].next){        int v = query[i].to;        if(vis[v])  ans[query[i].index] = dist[u] + dist[v] - 2 * dist[ance[_find(u)]];    }}int main(void){    int u, v, k;    int a, b, c;    int Q;    int T;scanf("%d", &T);    while(T--){        init();        scanf("%d%d", &n, &Q);        for(int i = 0; i < n - 1; i++){            scanf("%d%d%d",&a, &b, &c);            G[a].push_back(p(b, c));            G[b].push_back(p(a, c));        }        for(int i = 0; i < Q; i++){           scanf("%d%d",&u,&v);            add_query(u, v, i);        }        dist[1] = 0;        LCA(1);        for(int i = 0; i