圆方树

众所周知,圆方树是用以解决一类仙人掌图问题的重构树,但是类似的方法也可以用来解决某些普通无向图问题。依赖于其优美的树形结构,我们可以在 $\log |V|$ 的时间复杂度内回答一类图上的点对路径并集的询问问题……

定义

我们对一张联通无向图的每个 BCC(点双连通分量)建一个方点,原图上每个点作为一个圆点。对于不在环上的点,保留它们之间的边;对于环上的点,把它们和对应的方点相连边,就得到了一棵圆方树,如下图。

圆方树的构建

构建

这里使用的是 PinkRabbit 兔队的构建方法,用于一般无向图的圆方树构建。注意,对于仙人掌图的圆方树构建,可以在 dfs 中枚举返祖边来完成,它的好处在于能求出环上的点的顺序,以便于维护环上路径信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN * 20];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}
int n, m, dfn[CN], low[CN], idx = 0, stk[CN], top = 0, ext = n; vector<int> T[CN];
void bd(int u, int p){
dfn[u] = low[u] = ++idx, stk[++top] = u;
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to;
if(!dfn[v]){
bd(v, u), low[u] = min(low[u], low[v]);
if(low[v] == dfn[u]){
ext++; int pos = 0;
while(pos ^ v) pos = stk[top--], T[ext].push_back(v), T[v].push_back(ext);
T[ext].push_back(u), T[u].push_back(ext);
}
}
else low[u] = min(low[u], dfn[v]);
}
}

一道栗题

$n$ 个点 $m$ 条边的图,$q$ 次询问 $u,v$ 之间的割点的数量。
$n,m,q\le 5\times 10^5$

容易发现答案就是圆方树上 $u\to v$ 的路径上圆点的数量,倍增维护即可。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

const int CN = 1e6 + 6;

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

int n, m, q; vector<int> T[CN];

int dfn[CN], low[CN], idx = 0, stk[CN], top = 0, ext, fa[CN][21]; bool w[CN];
void bd(int u, int p){
dfn[u] = low[u] = ++idx, stk[++top] = u, w[u] = 1;
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to;
if(!dfn[v]){
bd(v, u), low[u] = min(low[u], low[v]);
if(low[v] == dfn[u]){
ext++, fa[ext][0] = u, T[u].push_back(ext);
int pos = 0;
while(pos ^ v) pos = stk[top--], fa[pos][0] = ext, T[ext].push_back(pos);
}
}
else low[u] = min(low[u], dfn[v]);
}
}

int dis[CN], dep[CN];
void dfs(int u, int p){
dep[u] = dep[p] + 1, dis[u] = dis[p] + w[u];
int sz = T[u].size();
for(int i = 0; i < sz; i++) dfs(T[u][i], u);
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
for(int k = 20; k + 1; k--) if(dep[ fa[u][k] ] >= dep[v]) u = fa[u][k];
if(u ^ v){
for(int k = 20; k + 1; k--) if(fa[u][k] ^ fa[v][k]) u = fa[u][k], v = fa[v][k];
u = fa[u][0];
}
return u;
}

int main()
{
ext = n = read(), m = read();
while(m--){
int u = read(), v = read();
add(u, v), add(v, u);
}

bd(1, 0), dfs(1, 0);
for(int k = 1; k <= 20; k++) for(int i = 1; i <= n; i++) fa[i][k] = fa[ fa[i][k - 1] ][k - 1];

q = read();
while(q--){
int x = read(), y = read(), l = lca(x, y);
printf("%d", dis[x] + dis[y] - dis[l] - dis[ fa[l][0] ]), puts("");
}

return 0;
}

又一道栗题

$n$ 个点 $m$ 条边的图,问有多少三元组 $(s,c,f)$ 满足存在一条 $s\to f$ 的路径经过 $c$。
$n,m\le 2\times 10^5$

题目本质上就是在求 $s\to f$ 的简单路径的并集大小。

有一个经典结论:

  1. 一张无向图上相同 BCC 中两个点 $(u,v)$ 之间的简单路径并集恰好是这个 BCC
  2. 一张无向图上不同 BCC 中两个点 $(u,v)$ 之间的简单路径并集是这两个 BCC 并上把它们连接的点

于是可以圆方树上的点恰当赋值:方点点权为该 BCC 的大小,圆点点权为 $-1$。那么 $s\to f$ 在树上的路径权就是合法的 $c$ 的数量。

考虑计算所有圆点对 $(s,f)$ 的路径长度和。运用贡献法去想,答案是每个 $w[u]$(即点权)乘上经过这个点的路径数量。经过 $u$ 的路径可以分为两种:从 $u$ 子树内到 $u$ 子树外;$u$ 子树内兄弟节点之间的路径。前者的数量是 $sz[u]\times (n-sz[u])$,后者的数量大概是 $\dbinom{sz[u]}{2}$ 再减去若干部分,直接在 dfs 的过程中计算即可,时间复杂度 $O(n)$。

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

const int CN = 4e5 + 6;

int read() {int s = 0,ne = 1; char c = getchar(); while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar(); while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar(); return s * ne;}

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

int n, m, q; vector<int> T[CN];

int dfn[CN], low[CN], idx = 0, stk[CN], top = 0, ext, w[CN], num;
void bd(int u, int p){
dfn[u] = low[u] = ++idx, stk[++top] = u, w[u] = -1, num++;
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to;
if(!dfn[v]){
bd(v, u), low[u] = min(low[u], low[v]);
if(low[v] == dfn[u]){
ext++, T[u].push_back(ext);
int pos = 0; w[ext] = 1;
while(pos ^ v) pos = stk[top--], T[ext].push_back(pos), w[ext]++;
}
}
else low[u] = min(low[u], dfn[v]);
}
}

long long ans = 0; int sz[CN];
void dfs(int u){
int l = T[u].size(); sz[u] = u <= n;
for(int i = 0; i < l; i++) dfs(T[u][i]), ans += 1ll * sz[u] * sz[ T[u][i] ] * w[u], sz[u] += sz[ T[u][i] ];
ans += 1ll * sz[u] * (num - sz[u]) * w[u];
}

int main()
{
freopen("_in.in", "r", stdin);

ext = n = read(), m = read();
while(m--){
int u = read(), v = read();
add(u, v), add(v, u);
}

for(int i = 1; i <= n; i++) if(!dfn[i]) num = 0, bd(i, 0), dfs(i);
printf("%lld", ans << 1);

return 0;
}

双一道栗题

$n$ 个点 $m$ 条边的图,点有点权,$q$ 次询问 $u\to v$ 的可行简单路径上权值最小值,支持修改点权。
$n,m,q\le 10^5$

注意到如果不带修改,直接圆方树上倍增即可。带修的话,显然的想法是重链剖分之后套个线段树。

但是这样有个问题,就是修改一个圆点需要修改所有与其相连的方点,这样实际上是 $O(n)$ 的。
我们考虑利用圆方树的性质,把方点的点权设为它的儿子的权值最小值,那么因为一个圆点至多有一个方点作为父亲,这样修改就变成了 $O(1)$ 的。
但是这样查询的时候如果方点的父亲没被访问到,即方点作为 lca 的情况,还需要对这个方点的父亲的权值取 $\min$。

时间复杂度 $O(n\log^2 n)$,常数不小,因为实际上我们需要一个 multiset 去维护方点的点权……

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;

const int CN = 2e5 + 5;
const int INF = 0x3f3f3f3f;

int read() {int s = 0,ne = 1; char c = getchar(); while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar(); while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar(); return s * ne;}

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

int n, m, q;

multiset<int> val[CN]; vector<int> T[CN];
int dfn[CN], low[CN], dfc = 0, w[CN], ext = 0, stk[CN], tp = 0;
void bd(int u, int p){
dfn[u] = low[u] = ++dfc, stk[++tp] = u;
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to;
if(!dfn[v]){
bd(v, u), low[u] = min(low[u], low[v]);
if(low[v] == dfn[u]){
int pos = 0; ext++;
while(pos ^ v)
pos = stk[tp--], T[ext].push_back(pos), val[ext].insert(w[pos]);
w[ext] = *val[ext].begin(), T[u].push_back(ext);
}
}
else low[u] = min(low[u], dfn[v]);
}
}

class SGT {
public: int d[CN << 2];
#define lc k << 1
#define rc k << 1 | 1
void md(int l, int r, int k, int p, int x){
if(l == r) return (void)(d[k] = x);
int m = (l + r) >> 1;
if(p <= m) md(l, m, lc, p, x); else md(m + 1, r, rc, p, x);
d[k] = min(d[lc], d[rc]);
}
int qu(int l, int r, int k, int s, int t){
if(s <= l && r <= t) return d[k];
int m = (l + r) >> 1, ans = INF;
if(s <= m) ans = qu(l, m, lc, s, t);
if(m < t) ans = min(ans, qu(m + 1, r, rc, s, t));
return ans;
}
} D;

int dep[CN], id[CN], idx = 0, top[CN], imp[CN], sz[CN], fa[CN];
void dfs1(int u, int p){
fa[u] = p, dep[u] = dep[p] + 1, sz[u] = 1; int mx = 0, l = T[u].size();
for(int i = 0; i < l; i++){
int v = T[u][i];
dfs1(v, u), sz[u] += sz[v], imp[u] = mx < sz[v] ? mx = sz[v], v : imp[u];
}
}
void dfs2(int u, int t){
id[u] = ++idx, D.md(1, ext, 1, id[u], w[u]), top[u] = t;
if(imp[u]) dfs2(imp[u], t); int l = T[u].size();
for(int i = 0; i < l; i++){
int v = T[u][i];
if(v ^ imp[u]) dfs2(v, v);
}
}

int qu(int x, int y){
int ans = INF;
while(top[x] ^ top[y]){
if(dep[ top[x] ] < dep[ top[y] ]) swap(x, y);
ans = min(ans, D.qu(1, ext, 1, id[ top[x] ], id[x]));
x = fa[ top[x] ];
}
if(dep[x] < dep[y]) swap(x, y);
ans = min(ans, D.qu(1, ext, 1, id[y], id[x]));
if(y > n) ans = min(ans, w[ fa[y] ]);
return ans;
}

int main()
{
freopen("_in.in", "r", stdin);

ext = n = read(), m = read(), q = read();
for(int i = 1; i <= n; i++) w[i] = read();
while(m--){
int u = read(), v = read();
add(u, v), add(v, u);
}

bd(1, 0), dfs1(1, 0), dfs2(1, 1);

while(q--){
char c; cin >> c; int a = read(), b = read();
if(c == 'C'){
D.md(1, ext, 1, id[a], b); int f = fa[a];
if(f > n){
val[f].erase(w[a]), val[f].insert(b);
if(*val[f].begin() ^ w[f]) w[f] = *val[f].begin(), D.md(1, ext, 1, id[f], w[f]);
}
w[a] = b;
}
else printf("%d", qu(a, b)), puts("");
}

return 0;
}

叒一道栗题

$n$ 个点 $m$ 条边的图,$q$ 次询问,每次询问给出一个点集 $S$,问有多少点满足在图上删除该点后,$\exists u,v\in S$,$u,v$ 在图上不连通。
$n,m\le 10^5, \sum|S_i|\le 2\times 10^5$

“圆方树上圆方果,
“圆方树下你和我,
“圆方树前建虚树,
“欢乐多又多。

Subtask2 $|S_i|=2$ 两点间割点数量等于圆方树上点对路径上的圆点数量,则直接在圆方树上倍增即可。
Subtask3 考虑建出圆方树的虚树来,然后就可以简单树形 DP 了,时间复杂度 $O(n)-O(|S_i|\log n)$。

代码:

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
92
93
94
95
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

const int CN = 4e5 + 5;

int read() {int s = 0,ne = 1; char c = getchar(); while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar(); while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar(); return s * ne;}

int TC, n, m, q, id[CN]; vector<int> G[CN], T[CN], S[CN];

int stk[CN], top = 0, dfn[CN], low[CN], idx = 0, ext;
void tarjan(int u, int p){
dfn[u] = low[u] = ++idx, stk[++top] = u;
int l = G[u].size();
for(int i = 0; i < l; i++){
int v = G[u][i];
if(!dfn[v]){ // dfn[] 需要清空!!!
tarjan(v, u), low[u] = min(low[u], low[v]);
if(dfn[u] == low[v]){
int pos = 0; T[u].push_back(++ext), T[ext].clear();
while(pos ^ v) pos = stk[top--], T[ext].push_back(pos);
}
}
else low[u] = min(low[u], dfn[v]);
}
}

int dep[CN], fa[CN][21], dis[CN];
void dfs(int u, int p){
dfn[u] = ++idx, fa[u][0] = p, dep[u] = dep[p] + 1, dis[u] = dis[p] + (u <= n);
int l = T[u].size();
for(int i = 0; i < l; i++) dfs(T[u][i], u);
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
for(int k = 20; k + 1; k--) if(dep[ fa[u][k] ] >= dep[v]) u = fa[u][k];
if(u ^ v){
for(int k = 20; k + 1; k--) if(fa[u][k] ^ fa[v][k]) u = fa[u][k], v = fa[v][k];
u = fa[u][0];
}
return u;
}

bool cmp(int i, int j) {return dfn[i] < dfn[j];} int rt;
void build(int a[], int n){
sort(a + 1, a + n + 1, cmp);
rt = stk[top = 1] = a[1], S[ a[1] ].clear();
for(int i = 2; i <= n; i++){
int u = a[i], l = lca(u, stk[top]); if(dfn[l] < dfn[rt]) rt = l;
if(l ^ stk[top]){
while(dfn[ stk[top - 1 ] ] > dfn[l]) S[ stk[top - 1] ].push_back(stk[top]), top--;
if(stk[top - 1] ^ l) S[l].clear(), S[l].push_back(stk[top]), stk[top] = l;
else S[l].push_back(stk[top--]);
}
S[u].clear(), stk[++top] = u;
}
for(int i = 1; i < top; i++) S[ stk[i] ].push_back(stk[i + 1]);
}

int f[CN];
void dp(int u){
int l = S[u].size(); f[u] = u <= n;
for(int i = 0; i < l; i++){
int v = S[u][i];
dp(v), f[u] += f[v] + dis[ fa[v][0] ] - dis[u];
}
}

int main()
{
freopen("_in.in", "r", stdin);

TC = read(); while(TC--){
ext = n = read(), m = read();
for(int i = 1; i <= n; i++) G[i].clear(), T[i].clear();
while(m--){
int u = read(), v = read(); G[u].push_back(v), G[v].push_back(u);
}

memset(dfn, 0, sizeof(dfn)), idx = top = 0, tarjan(1, 0), idx = 0, dfs(1, 0);
for(int k = 1; k <= 20; k++) for(int i = 1; i <= ext; i++) fa[i][k] = fa[ fa[i][k - 1] ][k - 1];

q = read();
while(q--){
id[0] = read(); for(int i = 1; i <= id[0]; i++) id[i] = read();
build(id, id[0]), dp(rt), printf("%d", f[rt] - id[0]), puts("");
}
}

return 0;
}

相关题目

  1. 「LG-P4320」道路相遇
  2. 「APIO2018」Duathlon
  3. 「CF487E」Tourists
  4. 「SDOI2018」战略游戏

习题
「LG-P5236」静态仙人掌

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×