Sweetlemon 的博客

Sweetlemon 的博客

奇妙的构造——IOI 2019 Day 1 T2 Split

posted on 2020-08-03 13:21:30 | under 题解 |

奇妙的构造——IOI 2019 Day 1 T2 Split

题意

题目链接

将一个简单无向连通图分为大小分别为 $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)题选讲的内容,本人进行了一些解释,在此表示感谢!

程序实现

给出我极长的代码,跑得似乎挺快的。

//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);
}