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));
        }
    }
}

动态仙人掌

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

Posted by xiaodao
Category: 日常