圆方树

圆方树

简介

圆方树可以处理一般的无向图。在圆方树中，一个圆点对应原图上的一个点，一个方点对应原图上的一个点双。圆方树中每条边连接一个圆点和一个方点。

模板

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
int n,m,cnt;
vector<int> g[N],T[N*2];
int dfn[N],low[N],dfc;
int stk[N],tp;
void tarjan(int u) 
{
	low[u]=dfn[u]=++dfc;
	stk[++tp]=u; 
	for(auto v:g[u]) 
    { 
		if(!dfn[v]) 
        { 
			tarjan(v);
			low[u]=min(low[u],low[v]); 
			if(low[v]==dfn[u]) 
            { 
				cnt++;
				for(int x=0;x!=v;tp--) 
                {
					x=stk[tp];
					T[cnt].push_back(x);
					T[x].push_back(cnt);
				}
				T[cnt].push_back(u);
				T[u].push_back(cnt);
			}
		} else low[u]=min(low[u],dfn[v]); 
	}
}

cnt=n;
// 处理非连通图
for(int u=1;u<=n;u++)
    if (!dfn[u]) tarjan(u),tp--;

例题

P4630 [APIO2018] 铁人两项

题意

给定一张简单无向图，问有多少对三元组 (s,c,f)(s,c,f) （s,c,fs,c,f 互不相同）使得存在一条简单路径从 ss 出发，经过 cc 到达 ff。

题解

点双有一个重要的性质：对于一个点双中的两点，它们之间简单路径的并集就是这个点双。由此我们可以得到：两点简单路径上的点集就是对应的两圆点在圆方树上的路径经过的方点相邻的圆点集合。

回到题目，固定 s,fs,f，合法的 cc 数量就是 s,fs,f 之间简单路径并集的点数减去 22。为此，我们可以给方点赋权值为对应点双的大小，每个圆点权值为 −1-1。这样，s,fs,f 圆方树上路径点权和就是 cc 的数量。剩下的就是一个经典问题，我们考虑每个点有多少条路径经过，这可以用树形dp解决。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,cnt;
vector<int> g[N],T[N*2];
int dfn[N],low[N],dfc;
int stk[N],tp;
int num,w[N*2],siz[N*2];
ll ans;
void tarjan(int u) 
{
	low[u]=dfn[u]=++dfc;
	stk[++tp]=u; 
    num++;
	for(auto v:g[u]) 
    { 
		if(!dfn[v]) 
        { 
			tarjan(v);
			low[u]=min(low[u],low[v]); 
			if(low[v]==dfn[u]) 
            { 
				cnt++;
				for(int x=0;x!=v;tp--) 
                {
					x=stk[tp];
					T[cnt].push_back(x);
					T[x].push_back(cnt);
                    w[cnt]++;
				}
				T[cnt].push_back(u);
				T[u].push_back(cnt);
                w[cnt]++;
			}
		} else low[u]=min(low[u],dfn[v]); 
	}
}
void dfs(int u,int fa)
{
    siz[u]=(u<=n);
    for(auto v:T[u])
    {
        if(v==fa) continue;
        dfs(v,u);
        ans+=2ll*w[u]*siz[u]*siz[v];
        siz[u]+=siz[v];
    }
    ans+=2ll*w[u]*siz[u]*(num-siz[u]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    cnt=n;
    for(int i=1;i<=n;i++) w[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    for(int u=1;u<=n;u++)
        if (!dfn[u]) 
        {
            num=0;
            tarjan(u),tp--;
            dfs(u,0);
        }
    cout<<ans<<'\n';
    return 0;
}

CF487E Tourists

题意

给定一张简单无向连通图，要求支持两种操作：

  • 修改一个点的点权
  • 询问两点之间所有简单路径上点权最小值。

题解

一个朴素的想法：建出圆方树，令方点权值为相邻圆点权值的最小值，则问题转化为求路径上最小值。可以用树剖+线段树维护。但是，在修改时，修改每个圆点需要同时修改所有相邻的方点，会被卡到 O(n)O(n)。

改进一下，令方点权值为自己儿子圆点的权值最小值，这样修改圆点时只需要修改父亲。对于每个方点，开一个multiset维护儿子圆点的权值集合即可。

注意：若查询时LCA是方点，则还需要查LCA父亲圆点的权值。