boxmoe_header_banner_img

Hello! 欢迎来到DRheEheAM的blog！

加载中

POST
文章导读
信息学

Jun. 27th~Jul. 1th | 圆方树

avatar
DRheEheAM_Garylv229憨毛怪 2026-07-01 48
0 评论

AI Summary

圆方树是将图转化为树的方法，用于解决路径上的割点、连通性、仙人掌图等题。

圆方树

基础知识

圆方树，是一种将图转化为树的方法。主要方法是找出图中的点双连通分量，对每个分量建一个方点，并连接原分量中每一个原来的点，建为圆点。最后我们能得到一棵树，便称为圆方树。

对于圆方树，有几个基础性质：

  • 圆方树的圆点编号 ≤n\le n ，方点编号 >n>n ，总节点数 ≤2n\le 2n ;
  • 圆方树上的任意一条路径是由圆点与方点交替出现的
  • 原图中的割边会拥有一割独立方点

接下来有几道题目

P4320 道路相遇

容易发现，这道题实际上在询问我们给定 u,vu,v ，求路径上的割点数量。

如果正常去枚举肯定不对，我们考虑建圆方树。

容易发现，实际上就是在问我们这两个圆点路径上有多少圆点。
圆方树依旧有一个性质，两个圆点路径上圆点的数量等于 l2+1\frac{l}{2}+1 （ ll 为路径长度）

那么直接使用 lca 即可

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=5e5+10;
int n,m;
vector <int> g[N],ng[N*2];
int dfncnt=0,pcnt=0,dfn[N],low[N];
stack <int> s;
void Tarjan (int u,int fa) {
    dfn[u]=low[u]=++dfncnt;
    s.push(u);
    for (int v:g[u]) {
        if (!dfn[v]) {
            Tarjan (v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                pcnt++;
                while (1) {
                    int su=s.top();
                    s.pop();
                    ng[pcnt].push_back(su);
                    ng[su].push_back(pcnt);
                    if (su==v) break;
                }
                ng[pcnt].push_back(u);
                ng[u].push_back(pcnt);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
int siz[N*2],hv[N*2],top[N*2],fa[N*2],dep[N*2];
void dfs1 (int u) {
    siz[u]=1;
    dep[u]=dep[fa[u]]+1;
    for (int v:ng[u]) {
        if (v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        siz[u]+=siz[v];
        if (siz[v]>siz[hv[u]]) hv[u]=v;
    }
}
void dfs2 (int u,int rt) {
    top[u]=rt;
    if (hv[u]) dfs2(hv[u],rt);
    for (int v:ng[u]) {
        if (v==fa[u]||v==hv[u]) continue;
        dfs2(v,v);
    }
}
int lca (int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return (dep[u]>dep[v]?v:u);
}
signed main() {
    Cios;
    cin>>n>>m;
    pcnt=n;
    for (int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    Tarjan(1,0);
    dfs1(1);
    dfs2(1,1);
    int q;
    cin>>q;
    while (q--) {
        int u,v;
        cin>>u>>v;
        cout<<(dep[u]+dep[v]-2*dep[lca(u,v)])/2+1<<"\n";
    }
    return 0;
}

P4630 [APIO2018] 铁人两项

这道题较上一道题更加复杂，我们考虑固定 cc 枚举 s,fs,f ，发现 ss 和 ff 在圆方树的不同子树中才会经过 cc 点。
那么我们只要枚举 cc 点的子树 vv 并得出 sizvsiz_v 表示子树 vv 中圆点个数。对于这个子树的答案就为 sizv×(tot−sizv)siz_v \times (tot-siz_v) （tottot为总节点个数）

因为这样统计依旧过于复杂，我们考虑任意点 uu 对总答案的贡献。
拆式子后得到：

  • 当 uu 为圆点时，res=−[T(T−1)−(T−szu)(T−szu−1)−∑szv×(szv−1)]\large res =-[T(T-1)-(T-sz_u)(T-sz_u-1)- \sum sz_v\times (sz_v-1)]
  • 当 uu 为方点时，res=wi×[T2−(T−szu)2−∑szv2]\large res=w_i\times[T^2-(T-sz_u)^2-\sum sz_v^2]

（其中 TT 表示连通块总大小， szusz_u 表示以 uu 为子树的节点数量，wiw_i表示 ii 方点对应的点双大小）

统计即可。

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e5+10,M=2e5+10;
int n,m;
vector <int> g[N],ng[N+M],nwc;
stack <int> st;
int cnt,dfncnt=0,dfn[N],low[N];
intl res,sz[N+M],wei[N+M];
void Tarjan (int u,int fa) {
    st.push(u);
    dfn[u]=low[u]=++dfncnt;
    for (int v:g[u]) {
        if (v==fa) continue;
        if (!dfn[v]) {
            Tarjan (v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                cnt++;
                while (1) {
                    int sv=st.top();
                    st.pop();
                    ng[sv].push_back(cnt);
                    ng[cnt].push_back(sv);
                    if (sv==v) break;
                }
                ng[u].push_back(cnt);
                ng[cnt].push_back(u);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
void dfs1 (int u,int fa) {
    nwc.push_back(u);
    for (int v:ng[u]) {
        if (v==fa) continue;
        dfs1(v,u);
    }
}
void dfs2 (int u,int fa,intl tot) {
    sz[u]=(u<=n);
    for (int v:ng[u]) {
        if (v==fa) continue;
        dfs2(v,u,tot);
        sz[u]+=sz[v];
    }
    intl pr=0;
    if (u<=n) {
        intl sum=0;
        for (int v:ng[u]) {
            if (v==fa) continue;
            sum+=(intl)sz[v]*(sz[v]-1);
        }
        sum+=(tot-sz[u])*(tot-sz[u]-1);
        pr+=tot*(tot-1)-sum;
    }
    else {
        intl sum=0;
        for (int v:ng[u]) {
            if (v==fa) continue;
            sum+=sz[v]*sz[v];
        }
        sum+=(tot-sz[u])*(tot-sz[u]);
        pr+=tot*tot-sum;
    }
    res+=pr*wei[u];
}
signed main() {
    Cios;
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cnt=n;
    for (int i=1;i<=n;i++) wei[i]=-1;
    for (int i=1;i<=n;i++) {
        if (!dfn[i]) {
            Tarjan (i,0);
            nwc.clear();
            st.pop();
            dfs1(i,0);
            intl tot=0;
            for (int u:nwc) {
                if (u<=n) tot++;
                else wei[u]=ng[u].size();
            }
            dfs2(i,0,tot);
        }
    }
    cout<<res<<"\n";
    return 0;
}

P4334 [COI 2007] Policija

这道题我们可以分情况讨论。

  • 对于询问边的，我们发现：
    • 当边不是割边时，不影响整图连通性，所以可以删去
    • 当边是割边时，我们需要求出路径是否经过这条割边
  • 对于询问点的，我们发现：
    • 当点不是割点时，不影响整图连通性，所以可以删去
    • 当点是割点时，我们需要求出路径是否经过这个割点

然后我们考虑圆方树，发现问题转换为了树上两个点的路径是否经过一个给定点的问题。因为无论是割边还是割点，在圆方树上都有对应的方点/圆点。

那我们假设 G1,G2G_1 ,G_2 的边对应方点编号也为 CC，那么求出 la,b=𝚕𝚌𝚊(a,b) , la,c=𝚕𝚌𝚊(a,c) , lb,c=𝚕𝚌𝚊(b,c)l_{a,b}=\texttt{lca}(a,b)\ ,\ l_{a,c}=\texttt{lca}(a,c)\ ,\ l_{b,c}=\texttt{lca}(b,c)

  • 当 la,b=cl_{a,b}=c 时证明经过，不能删去；
  • 当 la,c=cl_{a,c}=c 且 lb,c≠cl_{b,c}\not=c ，或是 lb,c=cl_{b,c}=c 且 la,c≠cl_{a,c}\not=c 也证明经过，不能删去；
  • 其余情况可以删去

分情况讨论即可。

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e5+10,M=5e5+10;
int n,e;
vector <int> g[N],ng[N+M];
int cnt,dfncnt=0,dfn[N],low[N];
stack <int> st;
map <pair<int,int>,int> mp;
void Tarjan (int u,int fa) {
    low[u]=dfn[u]=++dfncnt;
    st.push(u);
    for (int v:g[u]) {
        if (v==fa) continue;
        if (!dfn[v]) {
            Tarjan (v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                cnt++;
                if (low[v]>dfn[u]) mp[{min(u,v),max(u,v)}]=cnt;
                while (1) {
                    int sv=st.top();
                    st.pop();
                    ng[sv].push_back(cnt);
                    ng[cnt].push_back(sv);
                    if (sv==v) break;
                }
                ng[u].push_back(cnt);
                ng[cnt].push_back(u);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
int siz[N+M],fa[N+M],hv[N+M],top[N+M],dep[N+M];
void dfs1 (int u) {
    siz[u]=1;
    dep[u]=dep[fa[u]]+1;
    for (int v:ng[u]) {
        if (v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        siz[u]+=siz[v];
        if (siz[v]>siz[hv[u]]) hv[u]=v;
    }
}
void dfs2 (int u,int rt) {
    top[u]=rt;
    if (hv[u]) dfs2(hv[u],rt);
    for (int v:ng[u]) {
        if (v==fa[u]||v==hv[u]) continue;
        dfs2(v,v);
    }
}
int lca (int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]>dep[v]?v:u;
}
signed main() {
    Cios;
    cin>>n>>e;
    for (int i=1;i<=e;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cnt=n;
    Tarjan(1,0);
    dfs1(1);
    dfs2(1,1);
    int q;
    cin>>q;
    while (q--) {
        int op,a,b,g1,g2,c;
        cin>>op>>a>>b;
        if (op==1) {
            cin>>g1>>g2;
            c=mp[{min(g1,g2),max(g1,g2)}];
            if (c==0) {
                cout<<"yes\n";
                continue;
            }
        }
        else cin>>c;
        int lca_ab=lca(a,b),lca_ac=lca(a,c),lca_bc=lca(b,c);
        if (lca_ab==c) cout<<"no\n";
        else if ((lca_ac==c&&lca_bc!=c)||(lca_bc==c&&lca_ac!=c)) cout<<"no\n";
        else cout<<"yes\n";
    }
    return 0;
}

实际上，圆方树适合用于解决一种图的问题，即仙人掌图。

仙人掌图

图上任意一边最多存在于一个简单回路上的图称为仙人掌图。
通俗地讲，仙人掌图上任意一边要么是图的割边，要么是一个环上的边。且图上任意两个环最多有一个公共点，没有公共边。

P4129 [NEERC 2005 / SHOI2006] 仙人掌

分析题目，我们发现我们可以从任意多个环中删除至多一条边来得到支撑子图。

那么总答案数就是所有环上边的数量 +1+1 后相乘。

注意数据范围，答案 res≤1070000res\le 10^{70000} ，需要高精度。

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e5+10;
int n,m;
vector <int> g[N],ng[N];
int cnt,dfncnt=0,dfn[N],low[N],tag[N],siz[N];
stack <int> st;
void Tarjan (int u,int fa) {
    low[u]=dfn[u]=++dfncnt;
    st.push(u);
    for (int v:g[u]) {
        if (v==fa) continue;
        if (!dfn[v]) {
            Tarjan(v,u);
            if (low[v]<dfn[u]) {
                low[u]=min(low[u],low[v]);
                tag[u]++;
            }
            else if (low[v]>dfn[u]) st.pop();
            else {
                cnt++;
                siz[cnt]=1;
                while (1) {
                    int sv=st.top();
                    st.pop();
                    siz[cnt]++;
                    if (sv==v) break;
                }
            }
        }
        else if (low[v]<dfn[u]) {
            low[u]=min(low[u],dfn[v]);
            tag[u]++;
        }
    }
}
class Intl {
    int d[70005],dig=0;
    public:
    int operator [] (int idx) {return d[idx];}
    void operator *= (intl q) {
        intl tmp=0;
        for (int i=0;i<=dig;i++) {
            tmp+=d[i]*q;
            d[i]=tmp%10;
            tmp/=10;
        }
        while (tmp) {
            d[++dig]=tmp%10;
            tmp/=10;
        }
    }
    Intl (intl p) {
        dig=0;
        memset(d,0,sizeof d); 
        d[0]=p%10;
        p/=10;
        while (p) {
            d[++dig]=p%10;
            p/=10;
        }
    }
    void Output () {
        for (int i=dig;i>=0;i--) cout<<d[i];
        cout<<"\n";
    }
}res=1;
signed main() {
    Cios;
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int k,u,v;
        cin>>k>>u;
        for (int j=2;j<=k;j++) {
            cin>>v;
            g[u].push_back(v);
            g[v].push_back(u);
            u=v;
        }
    }
    Tarjan(1,0);
    bool fl=1;
    for (int i=1;i<=n;i++) {
        if (!dfn[i]||tag[i]>=2) {
            fl=0;
            break;
        }
    }
    if (!fl) cout<<"0\n";
    else {
        for (int i=1;i<=cnt;i++) res*=(siz[i]+1);
        res.Output();
    }
    return 0;
}

P5236【模板】静态仙人掌

建立圆方树。考虑如何设置边权。

我们将最先遍历到的环上的那个点（即 dfn 序最小的点）称作环顶，连一条权值为 00 的边到这个环的方点，其余任意一个环上的点连一条权值为这个点到环顶的最小距离的边。

考虑 lca。我们求出 u,vu,v 的 lca 记作 ll 。

如果 ll 是圆点直接计算；
如果 ll 是方点，那么我们就要找到 u,vu,v 进入环的那个点，分别记录到 u,vu,v 的距离，加上 u,vu,v 入环两点环上距离，得到总距离。

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=5e4+10;
int n,m,q;
struct edge {
    int to,w;
};
vector <edge> g[N],ng[N];
int dfncnt=0,cnt,dfn[N],low[N],fa[N],tovw[N],dep[N],tot[N],sum[N];
int nfa[N][20],ndep[N],ndis[N];
void Tarjan (int u) {
    dfn[u]=low[u]=++dfncnt;
    for (auto [v,w]:g[u]) {
        if (v==fa[u]) continue;
        if (!dfn[v]) {
            fa[v]=u;
            tovw[v]=w;
            dep[v]=dep[u]+w;
            Tarjan (v);
            low[u]=min(low[u],low[v]);
            if (low[v]>dfn[u]) {
                ng[u].push_back({v,w});
                ng[v].push_back({u,w});
            }
        }
        else {
            low[u]=min(low[u],dfn[v]);
            if (dfn[v]<dfn[u]) {
                cnt++;
                tot[cnt]=dep[u]-dep[v]+w;
                int cur=u;
                while (cur!=v) {
                    sum[cur]=dep[cur]-dep[v];
                    int mind=min(sum[cur],tot[cnt]-sum[cur]);
                    ng[cnt].push_back({cur,mind});
                    ng[cur].push_back({cnt,mind});
                    cur=fa[cur];
                }
                ng[v].push_back({cnt,0});
                ng[cnt].push_back({v,0});
            }
        }
    }
}
void dfs (int u) {
    ndep[u]=ndep[nfa[u][0]]+1;
    for (int i=1;i<20;i++) nfa[u][i]=nfa[nfa[u][i-1]][i-1];
    for (auto [v,w]:ng[u]) {
        if (v==nfa[u][0]) continue;
        nfa[v][0]=u;
        ndis[v]=ndis[u]+w;
        dfs(v);
    }
}
int lca (int u,int v) {
    if (ndep[u]<ndep[v]) swap(u,v);
    for (int i=19;i>=0;i--) {
        if (ndep[nfa[u][i]]>=ndep[v]) u=nfa[u][i];
    }
    if (u==v) return u;
    for (int i=19;i>=0;i--) {
        if (nfa[u][i]!=nfa[v][i]) {
            u=nfa[u][i];
            v=nfa[v][i];
        }
    }
    return nfa[u][0];
}
int jump (int u,int _dep) {
    for (int i=19;i>=0;i--) {
        if (ndep[nfa[u][i]]>=_dep) u=nfa[u][i];
    }
    return u;
}
signed main() {
    Cios;
    cin>>n>>m>>q;
    for (int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    cnt=n;
    Tarjan(1);
    dfs(1);
    while (q--) {
        int u,v;
        cin>>u>>v;
        int lc=lca(u,v);
        if (lc<=n) cout<<ndis[u]+ndis[v]-2*ndis[lc]<<"\n";
        else {
            int _u=jump(u,ndep[lc]+1),_v=jump(v,ndep[lc]+1);
            int res=ndis[u]-ndis[_u]+ndis[v]-ndis[_v];
            int oncd=abs(sum[_u]-sum[_v]);
            res+=min(oncd,tot[lc]-oncd);
            cout<<res<<"\n";
        }
    }
    return 0;
}
Tarjan 图论 圆方树

评论（0）

查看评论列表

暂无评论

发表评论

DRheEheAM_Gary Blog