P5236 【模板】静态仙人掌

· · 题解

这题是个圆方树板子

考虑把原图的点当做圆点，每一个环中间建一个方点

抓住一号点把仙人掌提起来，然后从一个环的顶点向方点连长为0的边，方点向环上其它点连长为这个点到顶点的距离的边

其实就是把一个环上的点到顶点的距离归到这个环的顶点上

这样你自下而上穿过这个环的算得的距离就是在树上的距离

所以询问就是在圆方树上求路径距离，特判一下如果lca是方点，也就是需要从左往右穿过环的距离

这个距离可以记录点在环上按一个方向走的距离和环的总长求解

这篇题解主要讲一些要处理的细节问题

以下内容都是我自己yy的，也不知道对不对，但是它过了你谷的数据，所以如果有大神hack了我麻烦告诉我，毕竟我太菜了/kk

关于重边产生的环的处理

这题数据里没有保证没有重边，但是我看前几篇题解似乎在tarjan里都是传的父节点的标号，然后强制不让tarjan往父节点走

但是这样显然就无法计算到大小为2的环了，当然这道题是求最短距离，还可以把边去重取最短的

我的想法是记录边的编号，然后强制不走过来的边，这样重边也可以被算到了

如何把一个环拿出来

这个地方我之前是从环的顶点出发，暴力枚举边，一个点一个点地找，特地写了个函数，特别麻烦，而且复杂度好像是错的？

我们知道tarjan过程中栈里存的点是按环上顺序排布的，那我们有没有什么办法在按顺序取出点的同时取出边呢？

我的想法是在每个点上维护一个标记表示环上遍历到它的边的长度，这样一个点就对应一条边，按顺序取点就是按顺序取边

想象一下tarjan其实实在dfs树上遍历，走到树边就递归，走到非树边就更新一下low[]

那么我们这个标记也是基于这个思路维护，对于一条边 (u \rightarrow v,l)

似乎跟神鱼写的差不多？

这样实现就不需要写一个跟tarjan一样长的连边函数了

下面放一下代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#define ll long long
using namespace std;
int read()
{
    int kkk=0,x=1;
    char c=getchar();
    while((c<'0' || c>'9') && c!='-') c=getchar();
    if(c=='-') c=getchar(),x=-1;
    while(c>='0' && c<='9') kkk=kkk*10+(c-'0'),c=getchar();
    return kkk*x;
}
int n,m,q,head[MAXN*2],tot=1,headn[MAXN*2],totn;
struct node
{
    int to,nextn,l;
}a[MAXN*2*2],an[MAXN*2];
void ADD(int from,int to,int l)
{
    a[++tot].to=to,a[tot].nextn=head[from],a[tot].l=l;
    head[from]=tot;
}
void ADDn(int from,int to,int l)
{
    an[++totn].to=to,an[totn].nextn=headn[from],an[totn].l=l;
    headn[from]=totn;
}
int size[MAXN],fa_len[MAXN],len[MAXN];
int dfn[MAXN],low[MAXN],tim,z[MAXN],top;
void tarjan(int u,int from)
{
    dfn[u]=low[u]=++tim;
    z[++top]=u;
    for(int i=head[u];i!=0;i=a[i].nextn)
    {
        int v=a[i].to;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            fa_len[v]=a[i].l;
            if(low[v]==dfn[u])
            {
                ++n;
                int las=0,cnt=1,mem=totn;
                size[n]=fa_len[u];
                ADDn(u,n,0);
                do
                {
                    las=z[top--];
                    ADDn(n,las,len[las]=size[n]);
                    size[n]+=fa_len[las];
                    ++cnt;
                }while(las!=v);
                for(int j=mem+1;j<=totn;++j) an[j].l=min(an[j].l,size[n]-an[j].l);
            }
            else if(low[v]>dfn[u]) --top,ADDn(u,v,a[i].l);
        }
        else if(i!=(from^1)) low[u]=min(low[u],dfn[v]),fa_len[v]=a[i].l;
    }
}
int deep[MAXN],jump[MAXN][22],dis[MAXN][22];
void format(int u,int fa)
{
    deep[u]=deep[fa]+1;
    int LOG=log2(deep[u]);
    jump[u][0]=fa;
    for(int i=1;i<=LOG;++i)
    {
        jump[u][i]=jump[jump[u][i-1]][i-1];
        dis[u][i]=dis[u][i-1]+dis[jump[u][i-1]][i-1];
    }
    for(int i=headn[u];i!=0;i=an[i].nextn)
    {
        int v=an[i].to;
        if(v==fa) continue;
        dis[v][0]=an[i].l;
        format(v,u);
    }
}
int ans;
int LCA(int &x,int &y)
{
    if(deep[x]<deep[y]) swap(x,y);
    int C=deep[x]-deep[y],LOG=log2(C);
    for(int i=0;i<=LOG;++i) if(C&(1<<i)) ans+=dis[x][i],x=jump[x][i];
    if(x==y) return x;
    LOG=log2(deep[x]);
    for(int i=LOG;i>=0;--i) if(jump[x][i]!=jump[y][i])
    {
        ans+=dis[x][i]+dis[y][i];
        x=jump[x][i],y=jump[y][i];
    }
    return jump[x][0];
}
int main()
{
    n=read(),m=read(),q=read();
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read(),l=read();
        ADD(u,v,l);
        ADD(v,u,l);
    }
    int tmp=n;
    for(int i=1;i<=tmp;++i) if(!dfn[i]) tarjan(i,0);
    format(1,0);
    while(q--)
    {
        ans=0;
        int x=read(),y=read(),lca=LCA(x,y);
        if(lca>tmp) printf("%d\n",ans+min(abs(len[x]-len[y]),size[lca]-abs(len[x]-len[y])));
        else if(x==y) printf("%d\n",ans);
        else printf("%d\n",ans+dis[x][0]+dis[y][0]);
    }
    return 0;
}