だから僕らは がんばって挑戦だよね

圆方树

  • ~8.98K 字
  1. 1. 简介
  2. 2. 描述
    1. 2.1. 性质
  3. 3. 算法
  4. 4. 题目
    1. 4.1. 无向图相关
      1. 4.1.1. [APIO2018] 铁人两项
      2. 4.1.2. CF487E Tourists

模拟赛考到了，正好写一下。

简介

圆方树是一种将图变成树的方法，解决一些路径连通性相关的东西或者是仙人掌。

描述

前置知识：点双连通分量。以下不考虑孤立点。

在圆方树中，原来的点为圆点，点双为方点。每个点双内部是一个菊花图 [1]，多个菊花图通过原图中的割点连接在一起。

圆方树有 n+cn+c 个点，cc 为原图中点双连通分量的个数。如果原图有 kk 个联通分量，那么圆方树会是有 kk 颗树的森林。

性质

圆方树有优美的性质。

  • 无论如何换根，圆方树形态不变
  • 圆方树的子树 = 原仙人掌的子仙人掌
  • 相同种类的点不会相连

算法

在找点双的时候，新找到一个点双就新建一个方点，与点双内部所有点连边即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int u,int father){
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    for(auto v:g[u]){
        if(!dfn[v]){
            dfs(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                nod++;
                do{
                    Tree::g[stk[top]].push_back(nod);
                    Tree::g[nod].push_back(stk[top--]);
                }while(stk[top+1]!=v);
                Tree::g[u].push_back(nod);
                Tree::g[nod].push_back(u);
            }
        }
        else if(v!=father)
            low[u] = min(low[u],dfn[v]);
    }
}

题目

无向图相关

[APIO2018] 铁人两项

建出圆方树，枚举中转点 cc 统计答案。

  • cc 为圆点，cc 的每一个儿子 vv 子树内的点都能和其他子树内的点组成合法的 (s,f)(s,f)，贡献为 sizev×(sizec−sizev−1)size_v \times (size_c-size_v-1)（sizesize 是原本的树的大小）。
  • cc 为方点，计算的是以这个点双中的某个点作为 cc，(s,f)(s,f) 中至少有一个点在点双内，且没有被圆点统计到的答案。(s,f)(s,f) 中有一个点在点双内，共有 degc−1deg_c-1 种，但是在割点出被圆点统计到了一次，所以有 degc−2deg_c-2 种。

用换根 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
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
typedef long long ll;
const int N = 200005;
ll ans;
int n,m;

namespace Tree{
    vector<int> g[N];
    int siz[N],fa[N],siz2[N],deg[N];

    void dfs1(int u){
        siz[u] = u<=n;
        for(auto v:g[u]){
            if(v==fa[u])
                continue;
            fa[v] = u;
            dfs1(v);
            siz[u] += siz[v];
        }
    }

    void dfs2(int u){
        if(fa[u])
            siz2[u] = siz2[fa[u]]+siz[fa[u]]-siz[u];
        for(auto v:g[u])
            if(v!=fa[u])
                dfs2(v);
        int sum = siz[u]+siz2[u];
        if(u<=n){
            for(auto v:g[u])
                if(v!=fa[u])
                    ans += (ll)(sum-siz[v]-1)*siz[v];
            ans += (ll)(sum-siz2[u]-1)*siz2[u];
        }
        else{
            for(auto v:g[u])
                if(v!=fa[u])
                    ans += (ll)(sum-siz[v])*siz[v]*(deg[u]-2);
            ans += (ll)(sum-siz2[u])*siz2[u]*(deg[u]-2);
        }
    }
}

namespace Graph{
    vector<int> g[N];
    int dfn[N],low[N],idx;
    int stk[N],top;
    int nod;

    void dfs(int u,int father){
        auto add = [](int a,int b){
            Tree::g[a].push_back(b);
            Tree::g[b].push_back(a);
            Tree::deg[a]++;
            Tree::deg[b]++;
        };
        dfn[u] = low[u] = ++idx;
        stk[++top] = u;
        for(auto v:g[u]){
            if(!dfn[v]){
                dfs(v,u);
                low[u] = min(low[u],low[v]);
                if(low[v]>=dfn[u]){
                    nod++;
                    do{
                        add(nod,stk[top--]);
                    }while(stk[top+1]!=v);
                    add(nod,u);
                }
            }
            else if(v!=father)
                low[u] = min(low[u],dfn[v]);
        }
    }

    inline void build(int u){
        if(!nod)
            nod = n;
        dfs(u,0);
    }
}

int main(){
    n = in(),m = in();
    for(int k=1;k<=m;k++){
        int a = in(),b = in();
        Graph::g[a].push_back(b);
        Graph::g[b].push_back(a);
    }
    for(int k=1;k<=n;k++)
        if(!Graph::dfn[k]){
            Graph::build(k);
            Tree::dfs1(k);
            Tree::dfs2(k);
        }
    out(ans);
    return 0;
}

CF487E Tourists

经过的点双的并就是所有可能路径的并，也就是问经过的所有点双中边权的最小值。

建圆方树，查询可以用树剖解决，问题在修改。

修改时计算更新所有相连的方点是不行的，菊花图就可以卡掉。

一个圆点的贡献挂到父亲上，父亲一定是方点。但是这样点双会缺一个点，缺的是深度最小的圆点，这个点被计算到了上方的点双里。

查询 x,yx,y 经过的点双除了包含 lca(x,y)lca(x,y) 的一定都能覆盖完全，缺的只有 lca(x,y)lca(x,y)。单独贡献 lca(x,y)lca(x,y) 即可，如果 lca(x,y)lca(x,y) 是方点则贡献 falca(x,y)fa_{lca(x,y)}。

对每个方点维护一个 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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
const int N = 200005;
int w[N];
int n,m;

namespace Tree{
    vector<int> g[N];
    int fa[N],dep[N],siz[N],son[N],top[N],dfn[N],idx;
    multiset<int> s[N];
    int m;

    class segtree{
        private:
            int tr[N<<2];

            inline void pushup(int x){
                tr[x] = min(tr[x<<1],tr[x<<1|1]);
            }
        public:
            segtree(){memset(tr,0x3f,sizeof(tr));}

            void update(int u,int l,int r,int x,int c){
                if(l==r){
                    tr[u] = c;
                    return;
                }
                int mid = (l+r)>>1;
                if(x<=mid)
                    update(u<<1,l,mid,x,c);
                else
                    update(u<<1|1,mid+1,r,x,c);
                pushup(u);
            }

            int query(int u,int l,int r,int L,int R){
                if(l>=L&&r<=R)
                    return tr[u];
                int mid = (l+r)>>1,ans = 1e9;
                if(L<=mid)
                    ans = min(ans,query(u<<1,l,mid,L,R));
                if(R>mid)
                    ans = min(ans,query(u<<1|1,mid+1,r,L,R));
                return ans;
            }
    }tr;

    void dfs1(int u){
        siz[u] = 1;
        for(auto v:g[u]){
            if(v==fa[u])
                continue;
            fa[v] = u;
            dep[v] = dep[u]+1;
            dfs1(v);
            siz[u] += siz[v];
            if(siz[v]>siz[son[u]])
                son[u] = v;
        }
    }

    void dfs2(int u,int tp){
        dfn[u] = ++idx;
        top[u] = tp;
        if(son[u])
            dfs2(son[u],tp);
        for(auto v:g[u]){
            if(v==fa[u]||v==son[u])
                continue;
            dfs2(v,v);
        }
    }

    inline void add(int x,int c,bool flag=true){
        if(flag&&fa[x])
            s[fa[x]].erase(s[fa[x]].find(w[x]));
        w[x] = c;
        if(!fa[x])
            return;
        s[fa[x]].insert(c);
        tr.update(1,1,m,dfn[fa[x]],*s[fa[x]].begin());
    }

    inline int query(int x,int y){
        int ans = 1e9;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])
                swap(x,y);
            ans = min(ans,tr.query(1,1,m,dfn[top[x]],dfn[x]));
            x = fa[top[x]];
        }
        if(dep[x]<dep[y])
            swap(x,y);
        ans = min(ans,tr.query(1,1,m,dfn[y],dfn[x]));
        if(y<=n)
            ans = min(ans,w[y]);
        else
            ans = min(ans,w[fa[y]]);
        return ans;
    }
}

namespace Graph{
    vector<int> g[N];
    int dfn[N],low[N],idx;
    int stk[N],top;
    int nod;

    void dfs(int u,int father){
        dfn[u] = low[u] = ++idx;
        stk[++top] = u;
        for(auto v:g[u]){
            if(!dfn[v]){
                dfs(v,u);
                low[u] = min(low[u],low[v]);
                if(low[v]>=dfn[u]){
                    nod++;
                    do{
                        Tree::g[stk[top]].push_back(nod);
                        Tree::g[nod].push_back(stk[top--]);
                    }while(stk[top+1]!=v);
                    Tree::g[u].push_back(nod);
                    Tree::g[nod].push_back(u);
                }
            }
            else if(v!=father)
                low[u] = min(low[u],dfn[v]);
        }
    }

    inline void build(){
        nod = n;
        dfs(1,0);
        Tree::m = nod;
    }
}

int main(){
    n = in(),m = in();
    int q = in();
    for(int k=1;k<=n;k++)
        w[k] = in();
    for(int k=1;k<=m;k++){
        int a = in(),b = in();
        Graph::g[a].push_back(b);
        Graph::g[b].push_back(a);
    }
    Graph::build();
    Tree::dfs1(1);
    Tree::dfs2(1,1);
    for(int k=1;k<=n;k++)
        Tree::add(k,w[k],false);
    while(q--){
        char ops = getchar();
        while(ops!='C'&&ops!='A')
            ops = getchar();
        int x = in(),y = in();
        if(ops=='C')
            Tree::add(x,y);
        else{
            out(Tree::query(x,y));
            putchar('\n');
        }
    }
    return 0;
}

  1. 存在一个点为支配点，其余点之间没有边相连，则这个图为菊花图（简单来说就是存在一个点与所有点相连，其余的点之间没有边）。 ↩︎

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可