圆方树/仙人掌学习笔记

shiroi · 2019-11-28 15:56:29 · 个人记录

仙人掌：每条边至多属于一个简单环的无向连通图。

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0; int f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1; ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

const int MAXN = 50005;
struct Node {int to,val;};
std::vector<Node> G[MAXN],adj[MAXN];
int dfn[MAXN],low[MAXN],fa[MAXN],sum[MAXN],dis[MAXN];
int top[MAXN],son[MAXN],size[MAXN],dep[MAXN],b[MAXN];
int n,m,q,cnt,ext;

inline int find(int x,int f)
{
    int res;
    while(top[x]!=top[f])
        res=top[x],x=fa[top[x]];
    return x==f?res:son[f];
}

inline int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

void dfs_getson(int x,int f)
{
    fa[x]=f; dep[x]=dep[f]+1; size[x]=1;
    int y,t=-1,l=adj[x].size();
    for(int i=0; i<l; ++i)
    {
        y=adj[x][i].to;
        if(y==f) continue;
        dis[y]=dis[x]+adj[x][i].val;
        dfs_getson(y,x); size[x]+=size[y];
        if(size[y]>t) t=size[y],son[x]=y;
    }
}

void dfs_rewrite(int x,int f)
{
    top[x]=f;
    if(son[x]==0) return;
    dfs_rewrite(son[x],f);
    int y,l=adj[x].size();
    for(int i=0; i<l; ++i)
    {
        y=adj[x][i].to;
        if(y==fa[x]||y==son[x]) continue;
        dfs_rewrite(y,y);
    }
}

inline void solve(int x,int y,int w)
{
    int pw,pre=w,i=y; ++ext;
    while(i!=fa[x])
        sum[i]=pre,pre+=b[i],i=fa[i];
    sum[ext]=sum[x]; sum[x]=0; i=y;
    while(i!=fa[x])
    {
        pw=min(sum[i],sum[ext]-sum[i]);
        adj[ext].push_back(Node{i,pw});
        adj[i].push_back(Node{ext,pw});
        i=fa[i];
    }
}

inline void tarjan(int x,int f)
{
    dfn[x]=low[x]=++cnt;
    int y,w,l=G[x].size();
    for(int i=0; i<l; ++i)
    {
        y=G[x][i].to;
        if(y==f) continue;
        w=G[x][i].val;
        if(!dfn[y])
        {
            fa[y]=x,b[y]=w; tarjan(y,x);
            low[x]=min(low[x],low[y]);
        }
        else low[x]=min(low[x],dfn[y]);
        if(low[y]<=dfn[x]) continue;
        adj[x].push_back(Node{y,w});
        adj[y].push_back(Node{x,w});
    }
    for(int i=0; i<l; ++i)
    {
        y=G[x][i].to;
        if(fa[y]==x || dfn[y]<=dfn[x]) continue;
        solve(x,y,G[x][i].val);
    }
}

int main(int argc, char const *argv[])
{
    n=read(); m=read(); q=read();
    int x,y,p,w; ext=n;
    for(int i=1; i<=m; ++i)
    {
        x=read(); y=read(); w=read();
        G[x].push_back(Node{y,w});
        G[y].push_back(Node{x,w});
    }
    tarjan(1,0); dfs_getson(1,0); dfs_rewrite(1,1);
    int sx,sy,ans;
    while(q--)
    {
        x=read(),y=read(),p=lca(x,y);
        if(p<=n) ans=dis[x]+dis[y]-(dis[p]<<1);
        else
        {
            sx=find(x,p),sy=find(y,p);
            ans=dis[x]+dis[y]-dis[sx]-dis[sy];
            if(sum[sx]<sum[sy]) swap(sx,sy);
            ans+=min(sum[sx]-sum[sy],sum[p]+sum[sy]-sum[sx]);
        }
        printf("%d\n", ans);
    }
    return 0;
}