处理仙人掌 ---> 首先建立出圆方树。则如果询问的两点 \(lca\) 为圆点，直接计算即可， 若 \(lca\) 为方点，则需要额外判断是走环的哪一侧（此时与两个点在环上的相对位置有关。）
#include <bits/stdc++.h> using namespace std; #define maxn 200000 #define int long long #define CNST 20 int n, m, Q, gra[maxn][CNST]; int N, dfn[maxn], low[maxn], timer; int S[maxn], dis[maxn], bk[maxn]; int dep[maxn], fa[maxn], id[maxn]; int A, B;struct edge {int cnp, head[maxn], to[maxn], last[maxn], w[maxn];edge() { cnp = 1; }void add(int u, int v, int ww){to[cnp] = v, last[cnp] = head[u], w[cnp] = ww, head[u] = cnp ++;to[cnp] = u, last[cnp] = head[v], w[cnp] = ww, head[v] = cnp ++;} }E1, E2;int read() {int x = 0, k = 1;char c;c = getchar();while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * k; }void Solve(int u, int v, int w) {N ++; int pre = w, ID = 0;bool flag = 0;for(int i = v; i != fa[u]; i = fa[i]){S[i] = pre; pre += bk[i];id[i] = ++ ID;}S[N] = S[u]; S[u] = 0;for(int i = v; i != fa[u]; i = fa[i]) E2.add(N, i, min(S[i], S[N] - S[i])); }void Tarjan(int u) {dfn[u] = low[u] = ++ timer; for(int i = E1.head[u]; i; i = E1.last[i]){int v = E1.to[i]; if(v == fa[u]) continue;if(!dfn[v]) bk[v] = E1.w[i], fa[v] = u, Tarjan(v), low[u] = min(low[u], low[v]);else low[u] = min(low[u], dfn[v]);if(low[v] > dfn[u]) E2.add(u, v, E1.w[i]);}for(int i = E1.head[u]; i; i = E1.last[i]){int v = E1.to[i];if(fa[v] != u && dfn[v] > dfn[u]) Solve(u, v, E1.w[i]);} }void dfs(int u, int ff) {gra[u][0] = ff; dep[u] = dep[ff] + 1;for(int i = 1; i < CNST; i ++) gra[u][i] = gra[gra[u][i - 1]][i - 1]; for(int i = E2.head[u]; i; i = E2.last[i]){int v = E2.to[i];if(v != ff) bk[v] = E2.w[i], dis[v] = dis[u] + E2.w[i], dfs(v, u);} }int LCA(int x, int y) {if(dep[x] < dep[y]) swap(x, y);for(int i = CNST - 1; ~i; i --)if(dep[gra[x][i]] >= dep[y]) x = gra[x][i];for(int i = CNST - 1; ~i; i --)if(gra[x][i] != gra[y][i]) x = gra[x][i], y = gra[y][i];A = x, B = y;return x == y ? x : gra[x][0]; }signed main() {n = read(), m = read(), Q = read();for(int i = 1; i <= m; i ++){int u = read(), v = read(), w = read();E1.add(u, v, w);}N = n; Tarjan(1); dfs(1, 0);while(Q --){int u = read(), v = read();int lca = LCA(u, v);if(lca <= n) printf("%lld\n", dis[u] + dis[v] - 2 * dis[lca]);else{int ans = dis[u] + dis[v] - dis[A] - dis[B];if(id[A] <= id[B]) swap(A, B);ans += min(S[A] - S[B], S[lca] - S[A] + S[B]);printf("%lld\n", ans);}}return 0; }