题解 P2325 【[SCOI2005]王室联邦】
Siyuan
2019-02-08 11:26:40
[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/articles/problem-SCOI-2005-Royal-Commonwealth/)
---
## Description
> 题目链接：[Luogu 2325](https://www.luogu.org/problemnew/show/P2325)
“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。他的国家有 $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
```cpp
#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;
}
```