BZOJ | Luogu
https://cmxrynp.github.io/2018/10/29/BZOJ-2125-%E6%9C%80%E7%9F%AD%E8%B7%AF/
https://blog.csdn.net/LPA20020220/article/details/88887231
题意
给你一个有 n 个点和 m 条边的仙人掌图，和 q 组询问，
每次询问两个点之间的最短路。
题解
圆方树
const int N = int(2e4) + 9, LV = 15;
VII adj[N], adjj[N];
int dfn[N], low[N], tt, sta[N], top;
int fa[LV][N], dep[N], D[N], DD[N], L[N];
int n, nn;
inline int move_up(int x, int t){
for (int lv=0;t;++lv,t>>=1)
if (t&1) x = fa[lv][x];
return x;
}
inline int lca(int x, int y) {
if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
return fa[0][x];
}
void getLCA(int x, int y, int &a, int &b, int &z) {
if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) {z = x; return;}
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
a = x; b = y; z = fa[0][x];
}
void add_edge(int u, int v, LL w) {
adjj[u].PB(MP(v, w));
}
#define v it->fi
#define w it->se
void tarjan(int u = 1, int p = -1) {
low[u] = dfn[u] = ++tt;
sta[++top] = u;
ECH(it, adj[u]) if (v != p) {
if (!dfn[v]) {
D[v] = D[u] + w; tarjan(v, u);
checkMin(low[u], low[v]);
if (dfn[v] == low[v]) add_edge(u, v, w); // tree edge
} else if (dfn[v] < dfn[u]) { // find circle
checkMin(low[u], dfn[v]);
add_edge(v, ++nn, 0); L[nn] = D[u]-D[v]+w;
for (int i=top;sta[i]!=v;--i) {
int d = D[sta[i]]-D[v];
add_edge(nn, sta[i], min(d, L[nn]-d));
}
}
}
--top;
}
#define p fa[0][u]
void dfs(int u = 1) {
ECH(it, adjj[u]) {
dep[v] = dep[u] + 1; DD[v] = DD[u] + w;
fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
dfs(v);
}
}
#undef p
#undef w
#undef v
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int Q, m; RD(n, m, Q);
DO(m) {
int x, y, w; RD(x, y, w);
adj[x].PB(MP(y, w));
adj[y].PB(MP(x, w));
}
nn = n; tarjan(); dfs();
DO(Q) {
int x, y, a, b, z; RD(x, y); getLCA(x, y, a, b, z);
//cout << x << " " << y << " " << z<< endl;
if (z <= n) { // round one ...
OT(DD[x]+DD[y]-DD[z]*2);
} else { // square one ...
int d = abs(D[a]-D[b]);
OT(DD[x]+DD[y]-DD[a]-DD[b]+min(d, L[z]-d));
}
}
}
