洛谷 P5811 [IOI2019] 景点划分 题解

神秘构造。

不难发现可以通过 BFS 从一个大小为 SS 的连通块里面提取出一个大小为 S′≤SS'\leq S 的连通块。于是让 A,B,CA,B,C 里面最大的集合不连通的方案是最容易构造的。

所以假设 a≤b≤ca\leq b\leq c，则原题相当于要求我们将原图里面所有点划分成两个点集 V1,V2V_1,V_2，使得 V1,V2V_1,V_2 的生成子图均连通，并且 ∣V1∣≥a,∣V2∣≥b|V_1|\geq a,|V_2|\geq b 或者 ∣V1∣≥b,∣V2∣≥a|V_1|\geq b,|V_2|\geq a。

由于 ∣V1∣+∣V2∣=n|V_1|+|V_2|=n，所以最后一个条件等价于 a≤∣V1∣≤n−ba\leq |V_1|\leq n-b 或 b≤∣V1∣≤n−ab\leq |V_1|\leq n-a。又注意到 b≤c<n−bb\leq c<n-b，所以该条件等价于 a≤∣V1∣≤n−aa\leq |V_1|\leq n-a。

考虑建出原图的圆方树。那么此时，任意一个节点的子树里面所有的圆点构成的点集一定是连通的，且任意一个节点的子树外面所有的圆点构成的点集也是连通的。

所以如果能找到一个子树，满足其中圆点的个数在 [a,n−a][a,n-a] 内，那么就做完了。

如果不能找到，也就是任意子树中圆点的个数 <a<a 或 >n−a>n-a，则圆方树上存在一个点，以这个点为根时，它的所有子树中圆点的个数都 <a<a。

如果这个点是一个圆点，那么说明原图中存在一个点，删去这个点以后图分为若干个大小 <a<a 的连通块。这显然是无解情况：选一个大小 ≥a\geq a 的连通块就一定会选到这个割点，然后就一定无法选一个大小 ≥b≥a\geq b\geq a 的连通块。

如果这个点是一个方点，那么让圆方树以该点为根，设其所有孩子分别为 u1,u2,⋯ ,uku_1,u_2,\cdots,u_k，其子树里面圆点的个数分别为 wu1,wu2,⋯ ,wukw_{u_1},w_{u_2},\cdots,w_{u_k}。

由于 u1,u2,⋯ ,uku_1,u_2,\cdots,u_k 构成一个点双连通分量，所以我们可以在它们之间建出一棵 DFS 树。如果这棵树上存在一个子树满足子树里面所有点的 ww 的和在 [a,n−a][a,n-a] 内，那么就找到了一个合法的划分。

如果仍不存在，则相当于存在一个 xx，满足 uxu_x 的子树里面的 ww 的和 >n−a>n-a 但是 uxu_x 的所有孩子的子树里面的 ww 的和 <a<a。

但是现在我们有两个很好的性质：

  • 树是一棵 DFS 树，所以所有非树边都是返祖边。
  • 原图点双连通，所以移除 uxu_x 以后图连通。

也就是说，对于任意一个 uxu_x 的孩子 vv，都存在一条非树边 ee 连接它的子树里面和 uxu_x 的子树外面。而如果我们将树边 (ux,v)(u_x,v) 从树里面删掉，将 ee 加入树，则 vv 的子树将会移动到 uxu_x 的子树外面。

所以我们的算法流程就是找到 uxu_x，并不断将 uxu_x 的孩子的子树移出，直到 uxu_x 的子树里面 ww 的和在 [a,n−a][a,n-a] 内。

注意到 a≤13n<23n≤n−aa\leq \dfrac{1}{3}n< \dfrac{2}{3}n\leq n-a，所以每次移出一个子树，uxu_x 的子树里面 ww 的和减少的量 <13n<\dfrac{1}{3}n，因此它不能直接从一个 >23n>\dfrac{2}{3}n 的值减少到一个 <13n<\dfrac{1}{3}n 的值，所以一定会有一个时刻落在 [a,n−a][a,n-a] 里面。

这样这道题就做完了，复杂度 O(n+m)O(n+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
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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
const int N = 0xAE3803 - 0xAA5100;

vector <int> g[N], tr[N], st[N];
int n, m, dfn[N], low[N], _time, stk[N], stktop, nds, siz[N], col[N], ncnt[4], nidx[4], fa[N], ans[N], ctr;
int w[N], wsm[N], vis[N], dvp;
queue <int> que;

inline void Read() {
    n = qread(); m = qread();
    for (int i = 1;i <= 3;i++) ncnt[nidx[i] = i] = qread();
    for (int i = 1;i <= m;i++) {
        int u = qread() + 1, v = qread() + 1;
        g[u].push_back(v); g[v].push_back(u);
    }
}

inline void Tarjan(int u, int fa) {
	dfn[u] = low[u] = ++_time;
	stk[++stktop] = u;
	for (int v : g[u]) {
		if (!dfn[v]) {
			Tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				nds++;
				for (;;) {
					int x = stk[stktop];
					stktop--;
					tr[nds].push_back(x);
					tr[x].push_back(nds);
					//cout << x << "<->" << nds << endl;
					if (x == v) break;
				}
				tr[u].push_back(nds);
				tr[nds].push_back(u);
				//cout << u << "<->" << nds << endl;
			}
		} else if (v != fa) low[u] = min(low[u], dfn[v]);
	}
}

inline void Dfs1(int u) {
    int mxsz = 0;
    siz[u] = (u <= n);
    for (int v : tr[u]) {
        if (v != fa[u]) {
            fa[v] = u;
            Dfs1(v);
            siz[u] += siz[v];
            mxsz = max(mxsz, siz[v]);
        }
    }
    mxsz = max(mxsz, n - siz[u]);
    if (mxsz <= n / 2) ctr = u;
}

inline void Dfs2(int u, int fa, int c) {
    col[u] = c;
    for (int v : tr[u]) {
        if (v != fa) Dfs2(v, u, c);
    }
}

inline void Prefix() {
    nds = n;
    Tarjan(1, -1);
    sort(nidx + 1, nidx + 4, [&](const int &x, const int &y) {
        return ncnt[x] < ncnt[y];
    });
}

inline void Dfs3(int u) {
    vis[u] = 2;
    for (int v : g[u]) {
        if (vis[v] == 1) {
            st[u].push_back(v);
            Dfs3(v);
        }
    }
}

inline void Dfs4(int u) {
    wsm[u] = w[u];
    for (int v : st[u]) {
        Dfs4(v); wsm[u] += wsm[v];
    }
}

inline void Dfs5(int u, int c) {
    col[u] = c;
    for (int v : st[u]) Dfs5(v, c);
}

inline void Divide() {
    Dfs1(1);
    for (int i = 1;i <= nds;i++) {
        if (siz[i] >= ncnt[nidx[1]] && n - siz[i] >= ncnt[nidx[2]]) {
            for (int j = 1;j <= n;j++) col[j] = nidx[2];
            Dfs2(i, fa[i], nidx[1]);
            return;
        }
        if (siz[i] >= ncnt[nidx[2]] && n - siz[i] >= ncnt[nidx[1]]) {
            for (int j = 1;j <= n;j++) col[j] = nidx[1];
            Dfs2(i, fa[i], nidx[2]);
            return;
        }
    }
    if (ctr <= n) return;
    for (int v : tr[ctr]) {
        if (v == fa[ctr]) w[v] = n - siz[ctr];
        else w[v] = siz[v];
        vis[v] = 1;
    }
    Dfs3(fa[ctr]); Dfs4(fa[ctr]);
    bool flg = 0;
    for (int v : tr[ctr]) {
        if (wsm[v] >= ncnt[nidx[1]] && n - wsm[v] >= ncnt[nidx[2]]) {
            for (int v : tr[ctr]) col[v] = nidx[2];
            Dfs5(v, nidx[1]);
            flg = 1;
            break;
        }
        if (wsm[v] >= ncnt[nidx[2]] && n - wsm[v] >= ncnt[nidx[1]]) {
            for (int v : tr[ctr]) col[v] = nidx[1];
            Dfs5(v, nidx[2]);
            flg = 1;
            break;
        }
    }
    if (!flg) {
        for (int u : tr[ctr]) {
            int mxs = 0;
            for (int v : st[u]) mxs = max(mxs, wsm[v]);
            if (mxs < ncnt[nidx[1]] && n - wsm[u] < ncnt[nidx[1]]) {
                int ndc = st[u].size();
                int cur = n - wsm[u];
                for (int i = 0;i < ndc;i++) {
                    cur += wsm[st[u][i]];
                    if (cur >= ncnt[nidx[1]] && n - cur >= ncnt[nidx[2]]) {
                        for (int v : tr[ctr]) col[v] = nidx[1];
                        col[u] = nidx[2];
                        for (int j = i + 1;j < ndc;j++) Dfs5(st[u][j], nidx[2]);
                        goto done;
                    }
                    if (cur >= ncnt[nidx[2]] && n - cur >= ncnt[nidx[1]]) {
                        for (int v : tr[ctr]) col[v] = nidx[2];
                        col[u] = nidx[1];
                        for (int j = i + 1;j < ndc;j++) Dfs5(st[u][j], nidx[1]);
                        goto done;
                    }
                }
            }
        }
        done:;
    }
    for (int v : tr[ctr]) Dfs2(v, ctr, col[v]);
}

inline void Bfs(int cid) {
    while (!que.empty()) que.pop();
    for (int i = 1;i <= n;i++) {
        if (col[i] == cid) {
            que.push(i);
            ans[i] = cid;
            break;
        }
    }
    int tot = 1;
    if (ncnt[cid] == 1) return;
    for (;;) {
        int u = que.front();
        que.pop();
        for (int v : g[u]) {
            if (col[v] == col[u] && ans[v] == nidx[3]) {
                ans[v] = cid;
                tot++;
                que.push(v);
                if (tot == ncnt[cid]) return;
            }
        }
    }
}

inline void Solve() {
    if (col[1] == 0) {
        for (int i = 1;i <= n;i++) cout << 0 << " ";
        cout << endl;
        return;
    }
    for (int i = 1;i <= n;i++) ans[i] = nidx[3];
    Bfs(nidx[1]); Bfs(nidx[2]);
    for (int i = 1;i <= n;i++) cout << ans[i] << " ";
    cout << endl;
}