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