题目概述

给一个 $n$ 个点 $m$ 条边的连通无向图，满足每条边最多属于一个环，有 $Q$ 组询问，每次询问两点之间的最短路径。

解题报告

不难想到建出圆方树，然后将距离转化为圆方树上的距离。

给定的是仙人掌，对于仙人掌，我们不需要用Tarjan来求圆方树（而且更麻烦），可以直接用DFS树：在找到返祖边 $u\to x$ 时，建立一个方点，将 $x$ 连向方点，然后从 $u$ 暴力向上跳，将方点连向途中的点，并且记录环的总距离。

圆方边的边权是点到祖先点的最小距离（环上有两个方向），用环的总距离以及DFS树上的距离就可以算出。

对于不在环中的边，我们在两个圆点之间连边权相同的边即可。

询问 $x,y$ 时，在圆方树上求出 $x,y$ 的 $lca$ ，然后讨论：

• $lca$ 是方点，那么先将 $x,y$ 跳到 $lca$ 的前一个节点 $fx,fy$ ，$x,y$ 走到 $fx,fy$ 之后再求环上的最小距离
• $lca$ 是圆点，那么答案就是 $x,y$ 在圆方树上的距离

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxm=100000,maxe=(maxm<<1)+maxn,LOG=18;

int n,N,m,Q,dfn[maxn+5],fa[maxn+5],lst[maxn+5];LL dis[maxn+5],sum[maxn+5];
int E,lnk[2][maxn+5],nxt[maxe+5],son[maxe+5];LL w[maxe+5];bool vis[maxe+5];
int ST[maxn+5][LOG+1],dep[maxn+5];LL pre[maxn+5];

inline void Add(int tp,int x,int y,LL z) {son[E]=y;w[E]=z;nxt[E]=lnk[tp][x];lnk[tp][x]=E++;}
void PBC(int x,int pre=-1){
    dfn[x]=++dfn[0];
    for (int j=lnk[0][x],u;~j;j=nxt[j])
        if ((j^1)!=pre)
            if (!dfn[u=son[j]]) fa[u]=x,lst[u]=j,dis[u]=dis[x]+w[j],PBC(u,j); else
            if (dfn[u]<dfn[x]){
                N++;Add(1,u,N,0);vis[j]=vis[j^1]=true;
                sum[N]=dis[x]-dis[u]+w[j];
                for (int i=x;i!=u;i=fa[i]){
                    Add(1,N,i,min(dis[i]-dis[u],sum[N]-(dis[i]-dis[u])));
                    vis[lst[i]]=vis[lst[i]^1]=true;
                }
            }
}
void DFS(int x,int fa=0){
    ST[x][0]=fa;dep[x]=dep[fa]+1;
    for (int j=1;j<=LOG;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[1][x],u;~j;j=nxt[j])
        u=son[j],pre[u]=pre[x]+w[j],DFS(u,x);
}
int LCA(int &x,int &y){
    if (dep[x]<dep[y]) swap(x,y);
    for (int j=LOG;~j && dep[x]>dep[y];j--) if (dep[ST[x][j]]>=dep[y]) x=ST[x][j];
    if (x==y) return x;
    for (int j=LOG;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];
    return ST[x][0];
}
int main(){
    scanf("%d%d%d",&n,&m,&Q);N=n;
    for (int i=1;i<=(n<<1);i++) lnk[0][i]=lnk[1][i]=-1;
    for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),Add(0,x,y,z),Add(0,y,x,z);
    PBC(1);
    for (int i=1;i<=n;i++)
        for (int j=lnk[0][i];~j;j=nxt[j])
            if (!vis[j] && dfn[son[j]]>dfn[i]) Add(1,i,son[j],w[j]);
    DFS(1);
    while (Q--){
        int x,y,fx,fy,lca;scanf("%d%d",&x,&y);
        if (x==y) {puts("0");continue;}
        fx=x;fy=y;lca=LCA(fx,fy);
        if (lca<=n) printf("%lld\n",pre[x]+pre[y]-(pre[lca]<<1)); else{
            LL ans=pre[x]-pre[fx]+pre[y]-pre[fy];
            if (dis[fx]>dis[fy]) swap(fx,fy);
            ans+=min(dis[fy]-dis[fx],sum[lca]-(dis[fy]-dis[fx]));
            printf("%lld\n",ans);
        }
    }
    return 0;
}