发表更新OI笔记21 分钟读完 (大约3080个字)

圆方树

众所周知，圆方树是用以解决一类仙人掌图问题的重构树，但是类似的方法也可以用来解决某些普通无向图问题。依赖于其优美的树形结构，我们可以在 $\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」静态仙人掌

圆方树

https://big-news.cn/2020/09/21/圆方树/

作者

ce-amtic

发布于

2020-09-21

更新于

2023-04-15

许可协议

CC BY-NC-SA 4.0

#

评论

目录

Your browser is out-of-date!

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

×

×