奇妙的构造——IOI 2019 Day 1 T2 Split
Sweetlemon
2020-08-03 13:21:30
## 奇妙的构造——IOI 2019 Day 1 T2 Split
### 题意
[题目链接](https://www.luogu.com.cn/problem/P5811)
将一个简单无向连通图分为大小分别为 $a,b,c$ 的三个集合，使得这三个集合中至少有两个是连通子图。
### 从部分分开始
首先考虑树的情况的部分分。我们只需要在树上找两个大小分别为 $a,b$ 的无交连通块即可。因为我们可以随便从连通块上删掉叶子节点，所以小的连通块总是更容易找到，于是我们可以设 $a\le b\le c$。
而找到了连通块后，我们可以往连通块上加节点，使得不属于 $A,B$ 两个点集的点进入这两个集合中的一个，最终使得 $A\cap B=\varnothing,A\cup B=G$。因此我们只需要把树划分成不相交的两个连通块，且这两部分的大小分别不小于 $a,b$ 即可。
考虑这两部分中不包含根的一部分，这一部分一定是以这个连通块的 LCA 为根的一棵子树（否则这个子树上不属于这个连通块的点无法与另一个连通块相连）。因此只需要在树上找到一棵大小在 $[a,n-b]$ 或 $[b,n-a]$ 内的子树即可。如果找不到这样的子树，就说明没有方案。找到了这棵子树，就从它和它的父亲开始分别向两边 dfs，染满 $a$ 个（或 $b$ 个）点后，剩下的点就染 $3$ 即可。
### 走向正解
现在考虑一般图的情况怎么做。选好连通块后，我们可以把无用的边删掉，形成一棵生成树；因此只要我们通过适当的方法造一棵生成树即可。
那么我们应该怎么选取这棵生成树呢？我们可以以 dfs 树为蓝本，通过调整得到这棵生成树。
先发掘 $a\le b\le c$ 中包含的信息。因为 $a+b+c=n$，因此 $a\le \frac{n}{3}$，$b\le \frac{n}{2}$，$c\ge \frac{n}{3}$（这些都可以用反证法证明）。我们只需要有一棵子树的大小在 $[a,n-b]$ 或 $[b,n-a]$ 内即可，由上面的范围可以推出 $n-b\ge b$，因此这两个区间中间没有空隙，它们的并是 $[a,n-a]$。而根据 $a$ 的范围，我们知道 $\left[\frac{n}{3},\frac{2n}{3}\right] \subseteq [a,n-a]$，可以看到这个范围其实是挺大的。
再看看我们“调整生成树”到底是什么样的过程。dfs 树上只有返祖边而没有横叉边，如果我们要“启用”一条返祖边，就必须“禁用”一条树边。这个过程中，禁用掉树边的父端节点子树的大小会减小，因此这可以看作是“剥离”一棵子树的方法。
那么我们想要把哪棵子树调整成合法呢？如果 dfs 树上本来就存在这样的子树，那么可以直接得解；如果目前不存在，我们可以选择“最深”且大小不小于 $n-a$ 的子树。什么叫“最深”呢？也就是，这个节点的子树不小于 $n-a$，但它所有子节点的子树都小于 $n-a$（根据“原来不存在这样的子树”知，如果小于 $n-a$ 那就一定小于 $a$）。
事实上，这样的节点存在且唯一。存在性很容易理解，毕竟根节点的子树大小为 $n$，肯定不小于 $n-a$。
唯一性呢？考虑反证法。如果存在两棵子树 $u,v$ 均满足条件，若 $u,v$ 没有祖先关系（这意味着这两棵子树无交），那么这两棵子树的大小之和不小于 $2(n-a)\ge \frac{4n}{3}$，矛盾；若 $u,v$ 有祖先关系，设 $u$ 是 $v$ 的祖先，考虑 $v$ 所在的 $u$ 的儿子 $x$（即考虑 $u$ 的那一个使得 $x$ 是 $v$ 父亲的儿子 $x$），有 $x$ 的子树的大小不小于 $v$ 的，这样也就不小于 $n-a$，于是 $u$ 有一个大小不小于 $n-a$ 的儿子，矛盾。
这样，我们就证明了这样的节点存在且唯一，可以用 dfs 找到这个节点，记为 $g$（记为 $g$ 是因为它有些类似重心）。而且，联系上面“唯一性”的证明，所有大小不小于 $n-a$ 的子树的根节点都是 $g$ 或 $g$ 的祖先。
$g$ 肯定比它的祖先更容易通过剥离子树而变为合法，因此我们只考虑处理 $g$。
把所有非树边（也就是返祖边）按照两端点分为三类：都在 $g$ 子树（包括 $g$）内、都在 $g$ 子树外或一端为 $g$ 而另一端在 $g$ 子树外、一端在 $g$ 子树内（且不为 $g$）而另一端在 $g$ 子树外。前两类的启用都对 $g$ 子树的大小没有影响，因此我们只能利用第三类边。
设一条“第三类边”的两端点为 $u,v$，其中 $u$ 是 $g$ 的祖先，$v$ 在 $g$ 子树内且不为 $g$。设 $v$ 所在的 $g$ 的儿子为 $x$，即 $x$ 是 $v$ 的祖先（包括 $v$）、$g$ 的儿子，那么我们只要把 $g-x$ 边禁用（变为非树边），再把 $u-v$ 边启用（变为树边），就剥离了 $x$ 子树，$g$ 子树的大小减小。由于 $x$ 子树的大小不超过 $a$，因此剥离 $x$ 子树后 $g$ 子树的大小不小于 $n-a-a=n-2a\ge n-\frac{2n}{3}=\frac{n}{3}\ge a$，也就是剥离 $x$ 子树后 $g$ 子树要么落入合法区间 $[a,n-a]$，要么仍大于 $n-a$。
因此，我们只要不断剥离这样的子树，直到 $g$ 子树的大小落入合法区间，那么就找到方案；如果剥离了所有可能的子树都不能让 $g$ 子树合法，那么就无解。
实现时，我们依次遍历 $g$ 的儿子 $x$，看 $x$ 子树内有没有能跳出 $g$ 子树的非树边，如果有就剥离 $x$，剥离后看 $g$ 子树的大小是否已经合法，合法就跳出循环。循环结束后，看 $g$ 子树的大小是否合法，如果合法则按树的部分分方法（只走树边遍历这个图）输出答案，否则输出无解。
这题全程只用到 dfs，复杂度只有 $\mathrm{O}(n)$，但构造非常巧妙，思维难度极大，需要仔细思考。
### 致谢
本文的方法基本来自王修涵在 WC 2020 上 Opencup 趣(duliu)题选讲的内容，本人进行了一些解释，在此表示感谢！
### 程序实现
给出我极长的代码，跑得似乎挺快的。
```cpp
//IOI 2019 D1T2
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAXIOLG 25
#define MOD 998244353
#define INF 19260817
#define MD(x) (((x)>=MOD)?((x)-=MOD):(0))
#define LOWBIT(x) ((x)&(-(x)))
#define FILENAME(x) \
freopen(x".in","r",stdin); \
freopen(x".out","w",stdout);
#define MAXN 100005
#define MAXM 400005
using namespace std;
typedef long long ll;
typedef long double ld;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快读
void ayano(io_t x,char spliter='\n'); //快写
typedef pair<int,int> pii;
pii cap_raw[4]; //存储原来的 a,b,c
int n,cap[4],point_g;
int ok_p=0,ok_q=0;
int visited[MAXN],sz[MAXN],depth[MAXN],par[MAXN];
int g[MAXM];
int fst[MAXN],nxt[MAXM],edges=1;
//edge_prop 为边的属性
//0 - 未定义, 1 - 父亲连向孩子的树边, 2 - 孩子连向父亲的树边, 3 - 非树边
int edge_prop[MAXM];
int anss[MAXN];
int dfs1(int x,int pa);
void dfs2(int x,int pa,int col);
void dfs3(int x,int pa);
void dfs4(int x,int pa,int col);
int dfs5(int x);
void addedge(int u,int v);
int main(void){
int m;
n=seto(),m=seto();
cap_raw[1]=make_pair(seto(),1),
cap_raw[2]=make_pair(seto(),2),
cap_raw[3]=make_pair(seto(),3);
sort(cap_raw+1,cap_raw+3+1); //a<=b<=c
cap[1]=cap_raw[1].first,cap[2]=cap_raw[2].first,cap[3]=cap_raw[3].first;
for (int i=1;i<=m;i++){
int u,v;
u=seto()+1,v=seto()+1;
addedge(u,v),addedge(v,u);
}
if (m==n-1){
//树的部分分
dfs1(1,0);
//没有找到合法子树
if (!ok_p){
for (int i=1;i<=n;i++)
ayano(0,' ');
putchar('\n');
return 0;
}
//从合法子树两端开始染色
dfs2(ok_p,ok_q,1),dfs2(ok_q,ok_p,2);
for (int i=1;i<=n;i++)
ayano(cap_raw[anss[i]].second,' ');
putchar('\n');
return 0;
}
//一般情况
dfs3(1,0);
if (ok_p){
//dfs 树上直接可以找到合法的子树
dfs4(ok_p,ok_q,1),dfs4(ok_q,ok_p,2);
for (int i=1;i<=n;i++)
ayano(cap_raw[anss[i]].second,' ');
putchar('\n');
return 0;
}
for (int ei=fst[point_g];ei;ei=nxt[ei]){
if (edge_prop[ei]==1 && dfs5(g[ei])){
//枚举 g 的儿子，看能否剥离
sz[point_g]-=sz[g[ei]]; //更新子树大小
edge_prop[ei]=edge_prop[ei^1]=3; //树边调整为非树边
if (sz[point_g]<=n-cap[1])
break;
}
}
if (sz[point_g]>n-cap[1]){
//不合法
for (int i=1;i<=n;i++)
ayano(0,' ');
putchar('\n');
return 0;
}
if (sz[point_g]<=n-cap[2]){
//size(g)<=n-b, 染成 1（a 对应的颜色）
ok_p=point_g,ok_q=par[point_g];
}
else {
//染成 2（b 对应的颜色）
ok_p=par[point_g],ok_q=point_g;
}
dfs4(ok_p,ok_q,1),dfs4(ok_q,ok_p,2);
for (int i=1;i<=n;i++)
ayano(cap_raw[anss[i]].second,' ');
putchar('\n');
return 0;
}
//树的部分分，计算 size
int dfs1(int x,int pa){
int tsz=1;
for (int ei=fst[x];ei;ei=nxt[ei]){
int v=g[ei];
if (v==pa)
continue;
tsz+=dfs1(v,x);
}
if (tsz>=cap[1] && tsz<=n-cap[2])
ok_p=x,ok_q=pa;
if (tsz>=cap[2] && tsz<=n-cap[1])
ok_p=pa,ok_q=x;
return tsz;
}
//树的部分分，染色
void dfs2(int x,int pa,int col){
if (!cap[col])
col=3; //如果染够了 a/b 个点，下面的点就染 3（c 对应的颜色）
anss[x]=col,cap[col]--;
for (int ei=fst[x];ei;ei=nxt[ei]){
int v=g[ei];
if (v==pa)
continue;
dfs2(v,x,col);
}
}
//制造 dfs 树
void dfs3(int x,int pa){
visited[x]=1;
sz[x]=1,depth[x]=depth[pa]+1,par[x]=pa;
int cond_1=1; //是否所有儿子的大小都小于 n-a
for (int ei=fst[x];ei;ei=nxt[ei]){
int v=g[ei];
if (v==pa){
edge_prop[ei]=2;
continue;
}
if (visited[v]){
edge_prop[ei]=3;
continue;
}
edge_prop[ei]=1;
dfs3(v,x);
sz[x]+=sz[v];
(sz[v]>n-cap[1])?(cond_1=0):(0);
}
if (sz[x]>=cap[1] && sz[x]<=n-cap[2])
ok_p=x,ok_q=pa;
if (sz[x]>=cap[2] && sz[x]<=n-cap[1])
ok_p=pa,ok_q=x;
if (cond_1 && sz[x]>n-cap[1])
point_g=x;
}
//走树边染色
void dfs4(int x,int pa,int col){
if (!cap[col])
col=3;
anss[x]=col,cap[col]--;
for (int ei=fst[x];ei;ei=nxt[ei]){
int v=g[ei];
if (v==pa || edge_prop[ei]>2 || anss[g[ei]])
continue;
dfs4(v,x,col);
}
}
//寻找合法非树边
int dfs5(int x){
int x_hs=0; //x 所连合法非树边编号
for (int ei=fst[x];ei;ei=nxt[ei]){
if (depth[g[ei]]<depth[point_g]){
x_hs=ei;
break;
}
}
if (x_hs){
edge_prop[x_hs]=2,edge_prop[x_hs^1]=1; //将非树边调整为树边
return 1;
}
for (int ei=fst[x];ei;ei=nxt[ei])
if (edge_prop[ei]==1)
if (dfs5(g[ei]))
return 1;
return 0;
}
void addedge(int u,int v){
edges++;
g[edges]=v;
nxt[edges]=fst[u],fst[u]=edges;
}
//快读
io_t seto(void){
io_t x=0;
int symbol=0;
char ch=getchar();
while (!isdigit(ch))
((ch=='-')?(symbol=1):(0)),ch=getchar();
while (isdigit(ch))
x=x*10+(ch-'0'),ch=getchar();
return (symbol)?(-x):(x);
}
//快写
void ayano(io_t x,char spliter){
if (!x){
putchar('0'),putchar(spliter);
return;
}
if (x<0)
putchar('-'),x=-x;
int ren=0;
while (x){
io_t d=x/10;
shin[ren++]=x-d*10;
x=d;
}
while (ren--)
putchar(shin[ren]+'0');
putchar(spliter);
}
```