LCA

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<stack>
#include<cstdlib>
#include<queue>
#include<set>
#include<string.h>
#include<vector>
#include<deque>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define eps 1e-4
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
typedef long long LL;
typedef long long ll;
const int maxn = 4e4 + 5;
const int mod = 998244353;

int cnt,DEG = 30;
int vis[maxn],head[maxn],dep[maxn],fa[maxn][30],dis[maxn];

struct EDGE {
    int next,to,v;
}edge[maxn * 2];

void addedge(int x,int y,int z) {
    edge[++cnt].to = y;
    edge[cnt].v = z;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
void init() {
    cnt = 0;
    memset(vis,0,sizeof vis);
    memset(head,-1,sizeof head);
    memset(dep,0,sizeof dep);
    memset(dis,0,sizeof dis);
}
void bfs(int root) {
    queue<int>que;
    dep[root] = 0;
    fa[root][0] = root;
    que.push(root);
    while(!que.empty()) {
        int tmp = que.front(); que.pop();
        for(int i = 1; i < DEG; i++) fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1];
        for(int i = head[tmp]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if(v == fa[tmp][0]) continue;
            dep[v] = dep[tmp] + 1;
            dis[v] = dis[tmp] + edge[i].v;
            fa[v][0] = tmp;
            que.push(v);
        }
    }
}
int LCA(int u,int v) {
    if(dep[u] > dep[v]) swap(u,v);
    int hu = dep[u],hv = dep[v],tu = u,tv = v;
    for(int det = hv - hu, i = 0; det; det >>= 1, i++) if(det & 1) tv = fa[tv][i];
    if(tu == tv) return tu;
    for(int i = DEG - 1; i >= 0; i--) {
        if(fa[tu][i] == fa[tv][i]) continue;
        tu = fa[tu][i];
        tv = fa[tv][i];
    }
    return fa[tu][0];
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t -- ) {
        init();
        int n, m;
        scanf("%d %d",&n,&m);
        for(int i = 1; i < n; i++) {
            int u,v,k;
            scanf("%d %d %d",&u,&v,&k);
            vis[v] = 1;
            addedge(u,v,k);
            addedge(v,u,k);
        }
        int root;
        for(int i = 1; i <= n; i++ ) {
            if(vis[i] == 0) {
                root = i;
                break;
            }
        }

        bfs(root);
        for(int i = 1; i <= m; i++) {
            int a,b;
            scanf("%d %d",&a,&b);
            int ans = dis[a] + dis[b] - 2 * dis[LCA(a,b)];
            printf("%d\n",ans);
        }
    }
}

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<stack>
#include<cstdlib>
#include<queue>
#include<set>
#include<string.h>
#include<vector>
#include<deque>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define eps 1e-4
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
typedef long long LL;
typedef long long ll;
const int maxn = 4e4 + 5;
const int mod = 998244353;

int cnt,DEG = 30;
int vis[maxn],head[maxn],dep[maxn],fa[maxn][30],dis[maxn];
//dep深度数组  fa[i][j]表示结点 i 的第2 ^ j个祖先
//dis[i] root到任意的一个i结点的距离
struct EDGE {
    int next,to,v;
}edge[maxn * 2];

void addedge(int x,int y,int z) {
    edge[++cnt].to = y;
    edge[cnt].v = z;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
void init() {
    cnt = 0;
    memset(vis,0,sizeof vis);
    memset(head,-1,sizeof head);
    memset(dep,0,sizeof dep);
    memset(dis,0,sizeof dis);
    memset(fa,0,sizeof fa);
}
void bfs(int root) {
    queue<int>que;
    dep[root] = 0;  //根节点的深度为0
    fa[root][0] = root;
    que.push(root);
    while(!que.empty()) {
        int tmp = que.front(); que.pop();
        for(int i = 1; i < DEG; i++)
            fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1]; //tmp这个点的2 ^ i的祖先就是 tmp的 2 ^ (i - 1)的祖先这个点的 2 ^ (i - 1)的祖先
        for(int i = head[tmp]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if(v == fa[tmp][0]) continue;
            dep[v] = dep[tmp] + 1;
            dis[v] = dis[tmp] + edge[i].v; //dis距离数组的更新
            fa[v][0] = tmp;
            que.push(v);
        }
    }
}
int LCA(int u,int v) {
    if(dep[u] > dep[v]) swap(u,v); //使得v的深度比较大
    int hu = dep[u],hv = dep[v],tu = u,tv = v;
    for(int det = hv - hu, i = 0; det; det >>= 1, i++)
        if(det & 1)
            tv = fa[tv][i];
    if(tu == tv)
        return tu;
    for(int i = DEG - 1; i >= 0; i--) {
        if(fa[tu][i] == fa[tv][i]) continue;
        tu = fa[tu][i];
        tv = fa[tv][i];
    }
    return fa[tu][0];
}
int main() {

    init();
    int n, m;
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 1; i <= m; i++) {
            int u, v, k;
            char s[10];
            scanf("%d %d %d %s", &u, &v, &k, s);
            vis[v] = 1;
            addedge(u, v, k);
            addedge(v, u, k);
        }
        int root;
        for (int i = 1; i <= n; i++) {
            if (vis[i] == 0) {
                root = i;
                break;
            }
        }

        bfs(root);
        int k;
        scanf("%d", &k);
        for (int i = 1; i <= k; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            int ans = dis[a] + dis[b] - 2 * dis[LCA(a, b)];
            printf("%d\n", ans);
        }
    }

}

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<stack>
#include<cstdlib>
#include<queue>
#include<set>
#include<string.h>
#include<vector>
#include<deque>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define eps 1e-4
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
typedef long long LL;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 998244353;

struct Edge {
    int to,next,v;
}edge[maxn * 2];
const int DEG = 30;
int head[maxn],dep[maxn],fa[maxn][DEG],dis[maxn];
bool vis[maxn];
int pre[maxn];
int tot;
void init() {
    tot = 0;
    memset(dis,0,sizeof dis);
    memset(head,-1,sizeof head);
    memset(vis,false,sizeof vis);
    memset(dep,0,sizeof dep);
}
int find(int x) {
    if(pre[x] != x)
        return pre[x] = find(pre[x]);
    return x;
}
void combine(int x,int y) {
    int fx = find(x);
    int fy = find(y);
    if(fx != fy) {
        pre[fx] = fy;
    }
}
void addedge(int u,int v,int z) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    edge[tot].v = z;
    head[u] = tot++;
}
void BFS(int root) {
    queue<int>que;
    dep[root] = 0;
    fa[root][0] = root;
    que.push(root);
    while(!que.empty()) {
        int tmp = que.front(); que.pop();
        for(int i = 1; i < DEG; i++) fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1];
        for(int i = head[tmp]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if(v == fa[tmp][0]) continue;
            dep[v] = dep[tmp] + 1;
            dis[v] = dis[tmp] + edge[i].v;
            fa[v][0] = tmp;
            que.push(v);
        }
    }
}
int LCA(int u,int v) {
    if(dep[u] > dep[v]) swap(u,v);
    int hu = dep[u],hv = dep[v];
    int tu = u,tv = v;
    for(int det = hv - hu,i = 0; det ; det >>= 1, i++) if(det & 1) tv = fa[tv][i];
    if(tu == tv) return tu;
    for(int i = DEG - 1; i >= 0; i--) {
        if(fa[tu][i] == fa[tv][i]) continue;
        tu = fa[tu][i];
        tv = fa[tv][i];
    }
    return fa[tu][0];
}
int main() {
   
    int n, m, k;
    while(~scanf("%d %d %d",&n,&m,&k)) { 
        init();
        for (int i = 1; i <= n; i++)
            pre[i] = i;
        for (int i = 0; i < m; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            addedge(a, b, c);
            addedge(b, a, c);
            combine(a, b);
            vis[b] = true;
        }
        int root;
        for (int i = 1; i <= n; i++) {
            if (vis[i] == false) {
                root = i;
                break;
            }
        }
        for (int i = 1; i <= n; i++)
            if (pre[i] == i)
                BFS(i);
        while (k--) {
            int a, b;
            scanf("%d %d", &a, &b);
            if (find(a) != find(b))
                puts("Not connected");
            else {
                int ans = dis[a] + dis[b] - 2 * dis[LCA(a, b)];
                printf("%d\n", ans);
            }
        }
    }
}