How far away ？

​​How far away ？​​

预处理出每一个节点到根节点的距离即可，两个节点之间的距离为​​len[x]+len[y]-2*len[lca(x,y)]​​

// Created by CAD
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;

const int maxn=4e4+5;
vector<pii> g[maxn];
int f[maxn][30],dep[maxn],len[maxn];
int lg[maxn];

void dfs(int x,int fa,int w){               //预处理出深度，父亲节点
    f[x][0]=fa,dep[x]=dep[fa]+1,len[x]=len[fa]+w;
    for(int i=1;i<=lg[dep[x]];++i)
        f[x][i]=f[f[x][i-1]][i-1];
    for(auto i:g[x])
        if(i.fi!=fa) dfs(i.fi,x,i.se);
}
int lca(int x,int y){                       //倍增法求最近公共祖先
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]-1];
    if(x==y) return x;
    for(int k=lg[dep[x]]-1;k>=0;--k)
        if(f[x][k]!=f[y][k])
            x=f[x][k],y=f[y][k];
    return f[x][0];
}
int main() {
    for(int i=1;i<=maxn-1;++i)              //预处理出log_2(i)+1的值
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    int T;scanf("%d",&T);
    while(T--){
        int n,q;  scanf("%d%d",&n,&q);
        for(int i=1;i<=n;++i) g[i].clear();
        for(int i=1;i<=n-1;++i){
            int a,b,w;scanf("%d%d%d",&a,&b,&w);
            g[a].push_back({b,w});
            g[b].push_back({a,w});
        }
        dfs(1,0,0);
        while(q--){
            int x,y;scanf("%d%d",&x,&y);
            printf("%d\n",len[x]+len[y]-2*len[lca(x,y)]);
        }
    }
    return 0;
}

CAD加油！欢迎跟我一起讨论学习算法，