圆方树这个东西咕了好久都没学，今天一看还是比较简单的

先讲一下仙人掌的定义：任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

放几张图：

え、 放错了，不过还是比较形象的（估计就是仙人掌名字的又来吧）：

放一个真·仙人掌：

fromBZOJ1023\rm from BZOJ 1023

我自己画的仙人掌图：

考虑解决仙人掌上面问题，上面的环很讨厌，我们要想一种办法把环缩掉。

当然不能直接上tarjan\rm tarjan缩环，因为tarjan\rm tarjan会把很多性质破坏掉，比如两点之间距离之类。

考虑把环缩成菊花图：

我们叫原来仙人掌上面的点圆点，新加进的菊花图的中心节点为方点，这样形成一棵圆方树。

（其实圆方树就是这样一个简单的东西，把环萎♂进去形成一个菊花图，网上的很多题解都写复杂了）

为什么不是仙人掌不能建立圆方树？考虑这样一个图：

把它的（伪）圆方树建出来，变成介个样子：

发现这并不是一棵树，因为有环。造成这个环的本质是有一条边在两个环上面都出现了一次。

专业一点来说，对于一条边<u,v><u,v>，设它同时存在两个环建立出的两个菊花图的中心节点为s1,s2s_1,s_2，那么必有u−s1−v−s2u-s_1-v-s_2这个环。

按照边数排个序：非联通图<<树（其实是仙人掌）<<基环树（其实也是仙人掌）≤\le仙人掌≤\le非仙人掌的连通图

讲完定义之后，我们来看怎么实现：

静态仙人掌

P5236 【模板】静态仙人掌

仙人掌图上面求节点uu，vv之间最短路dd。

先建好一棵圆方树（tarjan\rm tarjan实现）：

考虑第一件事，上面标红的那些边边权怎么弄，才不能破坏最短路的性质，也就是说，从红色边上面走相当于从环上面走。

考虑先钦定一个环上面的点albalb，我们强制经过albalb，所以从uu到vv相当于u−alb−vu-alb-v

具体实现的时候，记录一个sumsum代表边权的前缀和。

考虑第二件事，如何查询两个节点之间最短路？

设lcalca为LCA(u,v)LCA(u,v)

1.1.lcalca为圆点：dd为树上uu，vv之间距离，即d=dis(u,v)d=dis(u,v)

2.2.lcalca为方点：较为复杂，因为方点连出的边不存在，所以不能直接像上面一样搞，设lcalca的儿子中为uu，vv两个节点的祖先的两个节点为aa，bb，这样说有些复杂，不妨画图理解。

如图，lcalca往aa，bb连的两条边是不存在的，所以不能经过，所以只能从uu向上跳到aa，然后在环上面走一段路程到bb，最后从bb往下跳到vv，所以d=dis(u,a)+dis(a,b)+dis(b,v)d=dis(u,a)+dis(a,b)+dis(b,v)

注意：在环上面走有两种走法，不能忘记

实现起来还是有点细节的。

#include <bits/stdc++.h>
#define MAXN 40005
#define MAXM 23
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
struct Edge{
    int to,len;
};
vector<Edge>G1[MAXN],G2[MAXN];//G1为原图，G2为圆方树
inline void _AddEdge1(int u,int v,int w){
    G1[u].push_back(Edge{v,w});
}
inline void AddEdge1(int u,int v,int w){
    _AddEdge1(u,v,w),_AddEdge1(v,u,w);
}
inline void _AddEdge2(int u,int v,int w){
    G2[u].push_back(Edge{v,w});
}
inline void AddEdge2(int u,int v,int w){
    _AddEdge2(u,v,w),_AddEdge2(v,u,w);
}
namespace Lca{
    int anc[MAXN][MAXM],dis[MAXN],dep[MAXN];
    void dfs(int u,int father){
        anc[u][0]=father;
        for (register int i=1;i<MAXM;++i){
            anc[u][i]=anc[anc[u][i-1]][i-1];
        }
        for (register int i=0;i<G2[u].size();++i){
            int v=G2[u][i].to,w=G2[u][i].len;
            if (v!=father){
                dep[v]=dep[u]+1;
                dis[v]=dis[u]+w;
                dfs(v,u);
            }
        }
    }
    inline int LCA(int u,int v){
        if (dep[u]<dep[v]) swap(u,v);
        for (register int i=MAXM-1;i>=0;--i){
            if (dep[anc[u][i]]>=dep[v]){
                u=anc[u][i];
            }
        }
        if (u==v){
            return v;
        }
        for (register int i=MAXM-1;i>=0;--i){
            if (anc[u][i]!=anc[v][i]){
                u=anc[u][i];
                v=anc[v][i];
            }
        }
        return anc[u][0];
    }
    inline int Jump(int u,int lca){//H♂p
        for (register int i=MAXM-1;i>=0;--i){
            if (dep[anc[u][i]]>dep[lca]){
                u=anc[u][i];
            }
        }
        return u;
    }
    inline int Dis(int u,int v){
        return dis[u]+dis[v]-dis[LCA(u,v)]*2;
    }
}
using namespace Lca;
int square;//方点
int sum[MAXN];//一个类似于前缀和的东西，求环上边权的时候可以方便地相减得出答案
namespace RS_Tree{//Round Square Tree ???
    int dfn[MAXN],low[MAXN],cnt,fa[MAXN],tofa[MAXN];
    void tarjan(int u,int father){
        dfn[u]=low[u]=++cnt;
        for (register int i=0;i<G1[u].size();++i){
            int v=G1[u][i].to,w=G1[u][i].len;
            if (v!=father){
                if (!dfn[v]){fa[v]=u;tofa[v]=w;tarjan(v,u);low[u]=min(low[u],low[v]);}
                else{low[u]=min(low[u],dfn[v]);}
                if (low[v]<=dfn[u]) continue;
                AddEdge2(u,v,w);//原来的仙人掌上面边不在环里面的边要保留
            }
        }
        for (register int i=0;i<G1[u].size();++i){
            int v=G1[u][i].to;
            if (fa[v]==u||dfn[v]<=dfn[u]) continue;
            //找到非树边
            ++square;//新建方点
            int s=G1[u][i].len,t=v;
            while (t!=fa[u]){//在环上面绕圈圈
                sum[t]=s;
                s+=tofa[t];
                t=fa[t];
            }
            sum[square]=sum[u];sum[u]=0;
            //求出整个圈上面边权之和，u多算了，所以设成0
            //为什么记录sum[square]哪？往下看
            t=v;
            while (t!=fa[u]){
                AddEdge2(t,square,min(sum[t],sum[square]-sum[t]));//加上不存在的边
                //其实就是把环上走的一大堆路程压到一条边上面
                //可以往前面绕，也可以后面绕，所以取一个min
                t=fa[t];
            }
        }
    }
}
using namespace RS_Tree;
int n,m;
int main(){
    n=read(),m=read();
    int q=read();
    for (register int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        AddEdge1(u,v,w);
    }
    square=n;
    tarjan(1,0);
    dfs(1,1);
    while (q--){
        int u=read(),v=read();
        int lca=LCA(u,v);
        if (lca<=n){//圆点
            printf("%d\n",Dis(u,v));
        }
        else {//方点
            int A=Jump(u,lca),B=Jump(v,lca);//前面说的a,b
            int ans=Dis(u,A)+Dis(B,v);
            if (sum[A]<sum[B]) swap(A,B);//避免负数（不知道alb在A,B的哪里）
            printf("%d\n",ans+min(sum[A]-sum[B],sum[lca]+sum[B]-sum[A]));
            //直接调用sum[lca]体现出记录sum[square]的好处
        }
    }
}

倍增写的，跑的比较慢。

咕咕

（我连LCT都不会哪）