Nebulyu's Blog

归档站

0%

圆方树

Posted on Edited on In ,

圆方树


圆方树

在仙人掌，无向点双连通分量图中，每条边至多只属于一个环。将原来的点视作圆点，环视作方点，重新建图，可以得到一颗圆点和方点交替的树。圆方树可以方便的处理涉及简单路径和仙人掌结构的问题。

广义圆方树没有对点双连通分量的限制，可以在任何图中构造。但他与一般圆方树最明显的差别就是把所有的割边视作一个环(误。一般来说，两者差别不大，为了简便，通常用广义圆方树就可以了。


[APIO2018] 铁人两项

题目链接:https://www.luogu.com.cn/problem/P4630

题意:给一张无重边自环的图，要求选取不同的起点s,终点t,任意不同点c,满足s到c和c到t有不相交路径。求所有合法s,t,c的方案总数。其中$n \leq 1e5,m \leq 2e5$。

分析:分析题意可知，s,c,t一定在同一条链上，那么对于一条端点为s,t的链，链上所有点都是满足条件的c点。找到所有链覆盖的点，就得到了s,t确定时c的数量。

现在的问题转化为求固定端点的链覆盖，这个也并不好解决，需要引入圆方树的一个性质。

这里直接应用粉兔大佬博客 https://www.cnblogs.com/PinkRabbit/p/10446473.html 中的原话，推导就不放了:
对于一个点双中的两点，它们之间简单路径的并集，恰好完全等于这个点双。即同一个点双中的两不同点 u,v 之间一定存在一条简单路径经过给定的在同一个点双内的一点 w。考虑两圆点在圆方树上的路径，与路径上经过的方点相邻的圆点的集合，就等于原图中两点简单路径上的点集。

s,t经过所有链上的点，等价于圆方树里s,t路径经过的所有圆点与方点相邻的圆点。这个结论虽然是从仙人掌图里推出来的，不过看来这里也很好用。

对s,t，c进行计数，就是对圆方树上s,t的路径做统计。方点无法直接和圆点并列处理，考虑用点权进行预处理。方点的权值就是所有相邻的圆点数，圆点权值设为0，这样c的数量就是路径中方点的权值和减去s,t两端了。

这样就转化为一个很经典的树形dp,可以换根，也可以直接做。每个点，每条边都遍历一次，复杂度为$O(m)$级别，轻松通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//建立圆方树，基于tarjan算法的改进
//最后需要--top，弹出根节点
void dfs1(int p){
    dfn[p]=low[p]=++tim,stk[++top]=p;
    ++cnt;
    for(auto x:ov[p]){
        if(dfn[x])low[p]=min(low[p],dfn[x]);
        else{
            dfs1(x);
            low[p]=min(low[p],low[x]);
            if(low[x]==dfn[p]){
                ++n2;
                int t=0;
                while(t^x)t=stk[top--],ov2[t].pb(n2),ov2[n2].pb(t);
                ///此处不应用p做判断
                ov2[n2].pb(p),ov2[p].pb(n2);
                val[n2]=ov2[n2].size();
            }
        }
    }
}
//进行树dp,注意s,t有标号，答案要乘2
void dfs2(int p,int f){
    siz[p]=(p<=n);
    for(auto x:ov2[p]){
        if(x==f)continue;
        dfs2(x,p);
        ans+=val[p]*siz[p]*siz[x]*2;
        siz[p]+=siz[x];
    }
    ans+=val[p]*siz[p]*(cnt-siz[p])*2;
}


ABC318g Typical Path Problem

题目链接:https://atcoder.jp/contests/abc318/tasks/abc318_g

题意:给一张简单无向连通图，给定s,c,t三个点，判断是否有起点s,终点t,经过点c的简单路径。其中$n,m \leq 2e5$。

分析:利用上一题的推导结果，可以将问题转化为，判断圆方树上s到t的链上是否有一个方点与c相邻。

这个可以用很多做法来解决了，注意到树中圆点和方点交替，可以用类似于普通树上点在路径的距离判断法来简单解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int dis[N];
//dfs求点间距离
void dfs2(int p){
    for(auto x:ov2[p])if(!dis[x])dis[x]=dis[p]+1,dfs2(x); 
}
int q1,q2,q3;
void solve(){
    ffor(i,1,n2)dis[i]=0;
    dis[q1]=1,dfs2(q1);
    int d=dis[q3];
    ffor(i,1,n2)dis[i]=0;
    dis[q2]=1,dfs2(q2);
    //手玩几种情况，可以发现如果s,t之间的距离+3>=c到s,t的距离和，则合法
    if(d+3>=dis[q1]+dis[q3])cout<<"Yes";else cout<<"No";
}


静态仙人掌最短路

题目链接:https://www.luogu.com.cn/problem/P5236

题意:给一张仙人掌图，即任意一条边至多只出现在一条简单回路的无向连通图。给出若干询问，每次给出一组点对，求出点对的最短距离。其中$n,q\leq1e4,m\leq2e4,w_i\leq1e5$。

分析:如果不管环，那么仙人掌就是一颗树 （废话。一个树形图之前求最短路是很容易的，求LCA并减去距离前缀就可以了。

把仙人掌根据圆方树的构造建图，考虑在树上处理点对间距离。圆点之间可以直接求，圆点和方点的交边就比较麻烦了，需要保证圆点a-方点-圆点b的距离和等于圆点ab之间的距离。

通过为树选根定向的策略可以进行简化，对于树链圆点f-方点p-圆点s，设定f-p的边权为0，p-s的边权为f到s在原图中的距离，这样沿树链上行的时候就可以直接统计了。

如果在查询时出现了LCA为方点的情况，即圆点s1-方点p-圆点s2这样的树链，就需要快速处理出同一个BCC中点间距离。这个情况在一次查询中最多只出现一次。

总结一下，对于一个询问，先求点对的LCA
1.LCA是圆点，说明沿着树链的方向可以在原图中得到最短路，按照一般树上距离的方法来做。
2.LCA是方点，说明两侧分别沿树链上跳，最后在与LCA方点代表的环上的祖先处取到最短路。先上跳至与LCA相邻的祖先，再求出环上两点的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
vector<pil>ov[N],ov2[N];
int dfn[N],low[N],tim;
int n,n2,m;
int stk[N],top;
int lop[N];
unordered_map<int,ll>mp[N],sqmp[N];
ll sqsum[N];
//根据BCC添加方点，并预处理环上两点距离
//这里出于偷懒就用了map
void create_loop(int p,int x){
    ++n2;
    int t=0,len=0;
    while(t^x)t=stk[top--],lop[++len]=t;
    lop[++len]=p;	ov2[p].pb(n2,0);
    ll sum=mp[lop[1]][lop[len]],pre=sum;
    ffor(i,1,len-1)sum+=mp[lop[i]][lop[i+1]];
    sqsum[n2]=sum;
    ffor(i,1,len-1){
        ll d=min(pre,sum-pre);
        sqmp[n2][lop[i]]=pre;
        pre+=mp[lop[i]][lop[i+1]];
        ov2[n2].pb(lop[i],d);
    }
}
//根据预处理，求出环sq上两点最短距离
ll loop_dis(int sq,int p1,int p2){
    ll d1=sqmp[sq][p1],d2=sqmp[sq][p2];
    ll d=abs(d1-d2);
    return min(d,sqsum[sq]-d);
}
//建圆方树
void dfs1(int p){
    dfn[p]=low[p]=++tim,stk[++top]=p;
    for(auto e:ov[p]){int x=e.first;
        if(dfn[x])low[p]=min(low[p],dfn[x]);
        else{
            dfs1(x);
            low[p]=min(low[p],low[x]);
            if(low[x]==dfn[p])create_loop(p,x);
        }
    }
}
int vis[N];
ll dis[N];
int anc[N][M+1],dep[N];
//倍增LCA预处理
void dfs2(int p){
    vis[p]=1;
    ffor(i,1,M)anc[p][i]=anc[anc[p][i-1]][i-1];
    for(auto e:ov2[p]){int x=e.first;
        if(vis[x])continue;
        dis[x]=dis[p]+e.second;
        anc[x][0]=p,dep[x]=dep[p]+1;
        dfs2(x);
    }
}
int LCA(int p1,int p2){
    if(dep[p2]>dep[p1])swap(p1,p2);
    rfor(i,M,0)if(dep[anc[p1][i]]>=dep[p2])p1=anc[p1][i];
    if(p1==p2)return p1;
    rfor(i,M,0)if(anc[p1][i]^anc[p2][i])p1=anc[p1][i],p2=anc[p2][i];
    return anc[p1][0];
}
//跳到与LCA相邻的祖先
int JMP(int p,int l){
    rfor(i,M,0)if(dep[anc[p][i]]>dep[l])p=anc[p][i];
    return p;
}
void init(){
    n2=n;
    ffor(i,1,n){
        if(dfn[i])continue;
        dfs1(i),top=0;
    }
    ffor(i,1,n)if(!vis[i])dfs2(i),anc[i][0]=i;
}
int q;
void solve(){
    ffor(i,1,q){
        int p1,p2;cin>>p1>>p2;
        int l=LCA(p1,p2);ll ans=0;
        //LCA为圆点，同树的处理
        if(l<=n)ans=dis[p1]+dis[p2]-dis[l]*2;
        //LCA为方点，答案为到祖先的距离和+祖先间的最短路
        else{
            int f1=JMP(p1,l),f2=JMP(p2,l);
            ans=dis[p1]-dis[f1]+dis[p2]-dis[f2]+loop_dis(l,f1,f2);
        }
        cout<<ans<<"\n";
    }
}