自动搬运

查看原文

来自洛谷，原作者为

	Siyuan Dream OIer.

搬运于2025-08-24 21:36:23，当前版本为作者最后更新于2019-02-08 11:26:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$$\Large\texttt{My Blog}$$

Description

题目链接：Luogu 2325

“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。他的国家有 $n$ 个城市，编号为 $1\dots n$。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。

为了防止管理太过分散，每个省至少要有 $B$ 个城市，为了能有效的管理，每个省最多只有 $3B$ 个城市。

每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。

一个城市可以作为多个省的省会。

数据范围：$1\le n\le 3000$

Solution

我们可以考虑这样一个构造方法：

1. 我们 $\text{DFS}$ 整棵树，处理每个节点时，将其一部分子节点分块，将未被分块的子节点返回到上一层。
2. 枚举 $u$ 的每个子节点 $v$，递归处理子树后，将每个子节点返回的未被分块的节点添加到集合 $S$ 中，一旦 $\vert S\vert\ge B$ 就把 $S$ 作为一个新的块并将 $u$ 作为省会，然后清空 $S$ 并继续枚举 $v$。
3. 处理完所有子树后，将 $u$ 也加入到集合 $S$ 中，此时在 $S$ 中的节点为未被分块的节点，将被返回到上一层，显然 $S$ 的大小最大为 $B-1$ 个子树节点 + $u$ 节点本身，即 $\vert S\vert\le B$。
4. 由于返回的集合的大小最大为 $B$，对于一个子树会对集合最多增加 $B-1$ 个节点，那么每个块的大小最大为 $2B-1$，满足条件。
5. 在 $\text{DFS}$ 结束后，集合 $S$ 中可能还有节点（最多有 $B$ 个），那么我们把这 $B$ 个节点并入最后一个块（以根节点为省会的最后一个块）中，那么这个块的大小最大为 $3B-1$，符合条件。

时间复杂度：$O(n)$

Code

#include <cstdio>

const int N=1e3+5,M=2e3+5;
int n,B,sz,cnt,tot,lnk[N],ter[M],nxt[M],st[N],rt[N],bel[N];

void add(int u,int v) {
	ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;
}
void dfs(int u,int p) {
	int cnr=sz;
	for(int i=lnk[u];i;i=nxt[i]) {
		int v=ter[i];
		if(v==p) continue;
		dfs(v,u);
		if(sz-cnr>=B) {
			rt[++cnt]=u;
			while(sz>cnr) bel[st[sz--]]=cnt;
		}
	}
	st[++sz]=u;
}
int main() {
	scanf("%d%d",&n,&B);
	for(int i=1;i<n;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs(1,0);
	if(!cnt) rt[++cnt]=1;
	while(sz) bel[st[sz--]]=cnt;
	printf("%d\n",cnt);
	for(int i=1;i<=n;++i) printf("%d%c",bel[i]," \n"[i==n]);
	for(int i=1;i<=cnt;++i) printf("%d%c",rt[i]," \n"[i==cnt]);
	return 0;
}