学习心得 - 数据结构 - 圆方树

· · 算法·理论

算法简介

这个算法是一种将无向图转换成树的算法，一般适用于仙人掌图（每一条边至多只在一环上的图），可能可以适用一般无向图。

生成方式

圆方树首先把图里的每一个点双连通分量作为一个方点，原来的点作为一个圆点，再把圆点和方点连接起来，就可以构造出一颗圆方树，如 OIwiki 图，总点量则变成 n+c(\leq 2n)（其实在边数 \leq 2n 的时候可以自然想到圆方树），增加了点双个数个点。这里要注意原图每一个连通分量都将构成一棵圆方树，而孤点一般不考虑，当做原始点。

因为圆方树与点双连通分量有关，所以生成方式和求点双连通分量很像，可以当做Tarjan 变种。

具体的，当我们发现遍历完一颗子树发现 low_v=dfn_p，那就说明这个点不存在更优的点双出现方式，则我们发现了一个以点 p 为根的点双，这时用栈记录的元素就可以取出，按照定义建树即可。

模版：\tt P4630 铁人两项

题意：给你一个简单无向图，问多少个点对 (u,v,w) 满足 u 到 v 的简单路径经过 w。

这题需要的性质：同一个点双中的两不同点 u,v 之间一定存在一条简单路径经过给定的在同一个点双内的另一点 w。证明看 OIwiki。

根据这个性质我们得到两点之间的合法点数其实就是在圆方树上的点数。我们可以把方点的点权设置为点双数量，圆点的点权是 -1（减去多余贡献），这时两圆点间圆方树上路径点权和，恰好等于原图中简单路径并集大小 -2（开头结尾多减了）。

之后我们就可以直接树形 dp。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;
int n,m,tw[N],id[N],low[N],dc,nc,ac;
int stk[N],top;
vector<int>e[N],t[N];
void dfs(int p,int fa){
    id[p]=low[p]=++dc;
    stk[++top]=p;
    ++ac;
    for(auto v:e[p])if(!id[v]){
        dfs(v,p);
        low[p]=min(low[p],low[v]);
        if(low[v]==id[p]){ // find a bcc
            tw[++nc]=0; // add a block node
            for(int w=0;w^v;--top){
                w=stk[top];
                // add an edge between block and round
                t[nc].push_back(w);
                t[w].push_back(nc);
                // update weight
                ++tw[nc];
            }
            // node p (start point)
            t[nc].push_back(p);
            t[p].push_back(nc);
            ++tw[nc];
        }
    }else low[p]=min(low[p],id[v]);
    return;
}
ll rsz[N],ans;
void dpdfs(int p,int fa){
    rsz[p]=(p<=n);
    for(auto v:t[p])if(v^fa){
        dpdfs(v,p);
        ans+=2ll*tw[p]*rsz[p]*rsz[v];
        rsz[p]+=rsz[v];
    }
    ans+=2ll*tw[p]*rsz[p]*(ac-rsz[p]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++) // round node = -1
        tw[i]=-1;
    nc=n;
    for(int i=1;i<=n;i++)if(!id[i]){
        ac=0,top=0;
        dfs(i,0);
        dpdfs(i,0);
    }
    cout<<ans;
    return 0;
}

::::