# 某岛

… : "…アッカリ～ン . .. . " .. .
July 23, 2020

## 题解

### 圆方树

const int N = int(2e4) + 9, LV = 15;

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&gt;&gt;=1)
if (t&amp;1) x = fa[lv][x];
return x;
}
inline int lca(int x, int y) {
if (dep[x]&gt;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 &amp;a, int &amp;b, int &amp;z) {
if (dep[x]&gt;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) {
}

#define v it-&gt;fi
#define w it-&gt;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] &lt; 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) {
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);
}

nn = n; tarjan(); dfs();

DO(Q) {
int x, y, a, b, z; RD(x, y); getLCA(x, y, a, b, z);

//cout &lt;&lt; x &lt;&lt; " " &lt;&lt; y &lt;&lt; " " &lt;&lt;  z&lt;&lt; endl;

if (z &lt;= 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));
}
}
}


### 动态仙人掌

https://www.luogu.com.cn/record/31868182