【魅影缝匠】选择一个沙盘格，将与它相邻的沙盘格形态值翻倍

· · 题解

看大佬们都是 O(n) 的构造，我太菜了，想不出这样解法，用一些随机化乱搞过去。

首先，不妨 a<b<c，构造大小为 a 和 b 的连通点集，因为如果存在一个大小为 c 的连通点集，一定可以在里面找一个大小为 a 和 b 的，也就是说，更小的连通点集更容易构造。

来看一棵树的情况。如果存在一个子树，大小为 x，如果满足 x\ge a 且 n-x\ge b，则可以在 x 的子树中找个大小为 a 的连通点集，在 x 的子树外面找一个大小为 b 的连通点集；x\ge b,n-x\ge a 同理。

找一棵生成树，可以想象用一种随机化的方法。对边随机打乱，加入生成树中，跑一遍构造。多随机几次生成树。

但显然，如果存在一个点度数接近 n，则这种方法的生成树中这个点的度数也会很大，导致很难找到答案。

有三种解决方法：

于是可以通过洛谷和 LOJ 的数据了。

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 5;

int n, m, a, b, c, p1, p2, p3, deg[N], t;
struct edge{
    int u, v;
}e[N];
int pe[N];
int la[N], ne[N], en[N], idx;
int size[N], fa[N], res[N];
mt19937 mrand(time(0));

inline void add(int a, int b)
{
    ne[ ++ idx] = la[a];
    la[a] = idx;
    en[idx] = b;
}
inline int gfa(int i) {return i == pe[i] ? i : pe[i] = gfa(pe[i]);}
inline void kruskal()
{
    shuffle(e + 1, e + m + 1, mrand);
    for(int i = 1; i <= n; i ++ ) pe[i] = i, la[i] = fa[i] = 0;
    idx = 0;
    int p = mrand() & 1;
    if(p)
    {
        for(int i = 1; i <= m; i ++ )
        {
            int x = gfa(e[i].u), y = gfa(e[i].v);
            if(x != y)
            {
                pe[x] = y;
                add(e[i].u, e[i].v), add(e[i].v, e[i].u);
            }
        }
    }
    else
    {
        for(int i = 1; i <= m; i ++ )
        {
            if(deg[e[i].u] + deg[e[i].v] >= n / 3) continue ;
            int x = gfa(e[i].u), y = gfa(e[i].v);
            if(x != y)
            {
                pe[x] = y;
                add(e[i].u, e[i].v), add(e[i].v, e[i].u);
            }
        }
        for(int i = 1; i <= m; i ++ )
        {
            if(deg[e[i].u] + deg[e[i].v] < n / 3) continue ;
            int x = gfa(e[i].u), y = gfa(e[i].v);
            if(x != y)
            {
                pe[x] = y;
                add(e[i].u, e[i].v), add(e[i].v, e[i].u);
            }
        }
    }
}

inline void dfs1(int u)
{
    size[u] = 1;
    for(int i = la[u]; i; i = ne[i])
    {
        int v = en[i];
        if(v != fa[u])
        {
            fa[v] = u;
            dfs1(v);
            size[u] += size[v];
        }
    }
}
inline void dfs2(int u, int fa, int &cnt, int t)
{
    res[u] = t;
    cnt -- ;
    for(int i = la[u]; i && cnt; i = ne[i])
    {   
        int v = en[i];
        if(!res[v] && v != fa) dfs2(v, u, cnt, t);
    }
}

bool check()
{
    kruskal(), dfs1(1);
    for(int i = 1; i <= n; i ++ )
    {
        if(size[i] >= a && n - size[i] >= b)
        {
            dfs2(i, fa[i], a, p1), dfs2(fa[i], i, b, p2);
            for(int i = 1; i <= n; i ++ ) if(!res[i]) res[i] = p3, c -- ;
            return 1;
        }
        if(size[i] >= b && n - size[i] >= a)
        {
            dfs2(i, fa[i], b, p2), dfs2(fa[i], i, a, p1);
            for(int i = 1; i <= n; i ++ ) if(!res[i]) res[i] = p3;
            return 1;
        }
    }
    return 0;
}

inline bool check1()
{
    shuffle(e + 1, e + m + 1, mrand);
    for(int i = 1; i <= m; i ++ ) add(e[i].u, e[i].v), add(e[i].v, e[i].u);
    int x = mrand() % n + 1, y = mrand() % (n - 1) + 1;
    if(x == y) y ++ ;
    if(mrand() & 7) y = t;
    if(x == y) y ++ ;
    res[x] = p1, res[y] = p2;
    int ca = a, cb = b;
    dfs2(x, 0, ca, p1), dfs2(y, 0, cb, p2);
    if(!ca && !cb)
    {
        for(int i = 1; i <= n; i ++ ) if(!res[i]) res[i] = p3;
        return 1;
    }
    for(int i = 1; i <= n; i ++ ) la[i] = res[i] = 0, idx = 0;
    return 0;
}

int main()
{
    scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
    p1 = 1, p2 = 2, p3 = 3;
    if(a > c) swap(a, c), swap(p1, p3);
    if(b > c) swap(b, c), swap(p2, p3);

    for(int i = 1; i <= m; i ++ ) scanf("%d%d", &e[i].u, &e[i].v), e[i].u ++ , e[i].v ++ , deg[e[i].u] ++ , deg[e[i].v] ++ ;
    for(int i = 1; i <= n; i ++ ) if(deg[i] > deg[t]) t = i;
    int k = 300000 / m;
    for(int i = 1; i <= k; i ++ ) if(check()) break ;
    if(!res[1])
    {
        memset(la, 0, sizeof la), idx = 0;
        for(int i = 1; i <= k; i ++ ) if(check1()) break ;
    }
    for(int i = 1; i <= n; i ++ ) printf("%d ", res[i]);
    return 0;
}