题解 P2325 【[SCOI2005]王室联邦】

· · 题解

\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;
}