[IOI2019] 景点划分

令人忍俊不禁的是，11 月的模拟赛出现了 “摩拉克斯” 一题，被取之。2 月 JOISC 出现这个模型，被取之。2 月模拟赛出现这个模型，被取之。本题再次出现这个模型，被取之。

呃呃呃呃呃呃呃呃呃啊。

首先进行一些简单的分析：令 \(A\le B\le C\)，构造 \(A,B\) 合法的情况即可。并且有 \(A\le n/3, B\le n/2\)。

直接做似乎不好做，从树的情况入手。

树上连通块划分：存在一条边使得两个划分的连通块分别在其两侧。

此时直接枚举已经可以做了，但是这个做法我不好搬到图上啊，仔细分析一番。

我觉得接下来的分析有点不自然，然而似乎是常用思路：注意到两个连通块必然有一个包含原树的重心，以重心为根，如果割掉 \((x,fa_x)\) 的方案合法，那么假设 \(x\) 所在的根的子树为 \(y\)，则割掉 \((y,rt)\) 合法。

于是把重心拿出来判断即可，如果所有子树都 \(<A\) 直接就寄了，否则有 \(A\le sz_x\le n/2\)，则 \(n-sz_x\ge n/2\ge B\)，于是得出判定条件和构造方法，这个就比较漂亮了。

回到原题，自然地想到拿出 DFS 树的重心进行考察，假设子树为 \(s_1,s_2,\dots ,s_k\)，父亲为 \(T\)。

首先执行上述树的构造，如果无解则 \(\forall i\in [1,k], |s_i|\le A\) 且 \(|T|\le A\)。

由于 DFS 树的性质，会有一些边将 \(s\) 和 \(T\) 相连。如果这些 \(s\) 和 \(T\) 拼起来都不行就还是寄了，否则选几个 \(s\) 和 \(T\) 拼起来，使得 \(A\le siz\le 2A\)，又因为 \(2A+B\le A+B+C=n\) 所以剩下的部分可以凑出一个 \(B\)。问题得到了解答。

感觉是挺漂亮的题目，从树的情况出发，自然的通过 DFS 树搬到图上，并且运用了代数上的简单处理。

放一下代码，感觉我写的还行，只有 2.4k。

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using pii = std::pair<int, int>;

constexpr int maxn = 1e5 + 5;
int A, B, n, m, fa[maxn], siz[maxn], mxv[maxn], bel[maxn], rt, dep[maxn], low[maxn];
std::vector<int> G[maxn], E[maxn];

void chkmax(int& x, int y) { if (y > x) x = y; return ; }
void chkmin(int& x, int y) { if (y < x) x = y; return ; }

void dfs(int u, int ff) {
	fa[u] = ff;
	dep[u] = dep[ff] + 1;
	low[u] = dep[u];
	siz[u] = 1;
	mxv[u] = 0;
	for (auto& v : G[u]) {
		if (dep[v]) {
			chkmin(low[u], dep[v]);
			continue ;
		}
		dfs(v, u);
		siz[u] += siz[v];
		E[u].pb(v);
		chkmin(low[u], low[v]);
		chkmax(mxv[u], siz[v]);
	}
	if (ff) E[u].pb(ff);
	chkmax(mxv[u], n - siz[u]);
	if (mxv[u] < mxv[rt]) rt = u;
	return ;
}

bool ban[maxn];

void dfs2(int u, int ff, int& res, int typ) {
	if (!res) return ;
	--res;
	bel[u] = typ;
	for (auto& v : E[u]) {
		if (v == ff || ban[v]) continue ;
		dfs2(v, u, res, typ);
		if (!res) return ;
	}
	return ;
}

int Nosol() {
	for (int i = 1; i <= n; ++i)
		std::cout << "0 ";
	return std::cout << "\n", 0;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	std::cin >> n >> m;
	std::vector<std::pair<int, int>> qry(3);
	for (int i = 0; i < 3; ++i)
		std::cin >> qry[i].fir, qry[i].sec = i + 1;
	std::sort(qry.begin(), qry.end());
	A = qry[0].fir;
	B = qry[1].fir;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		std::cin >> u >> v;
		++u;
		++v;
		G[u].pb(v);
		G[v].pb(u);
	}
	mxv[0] = 114514;
	dfs(1, 0);
	std::fill(bel + 1, bel + 1 + n, 2);
	if (mxv[rt] >= A) {
		int pos = 0;
		ban[rt] = true;
		for (auto& v : E[rt]) {
			int sz = v == fa[rt] ? n - siz[rt] : siz[v];
			if (sz >= A) {
				dfs2(v, 0, A, 0);
				pos = v;
				break ;
			}
		}
		ban[rt] = false;
		ban[pos] = true;
		dfs2(rt, 0, B, 1);
	} else {
		std::vector<int> g;
		int tot = n - siz[rt];
		for (auto& v : E[rt]) {
			if (v == fa[rt] || low[v] >= dep[rt]) continue ;
			g.pb(v);
			tot += siz[v];
		}
		if (tot < A) return Nosol();
		ban[rt] = true;
		if (fa[rt]) {
			dfs2(fa[rt], 0, A, 0);
			ban[fa[rt]] = true;
		}
		for (auto& v : g) {
			if (A <= 0) break ;
			dfs2(v, 0, A, 0);
			ban[v] = true;
		}
		ban[rt] = false;
		dfs2(rt, 0, B, 1);
	}
	for (int i = 1; i <= n; ++i)
		std::cout << qry[bel[i]].sec << ' ';
	return 0;
}