P2325 （树上分块）题解

· · 题解

本文同步发表至我的WordPress博客，阅读体验可能更佳。

原题面

Update On 2021.1.6：更新了代码注释，求不被咕。

题意：

把一个有 n 个点的树划分成若干个省，要求每个省至少要有 B 个城市，最多可以有 3B 个城市。

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

思路：

树上分块。我们考虑直接从根开始边跑DFS边划分，把每个需要划分的点放进一个栈 Sta 。

划分方法：

  1. 枚举 x 的每个子节点 v，递归处理子树后，将每个子节点返回的未被分块的节点压到栈 Sta 中（后面会讲到），一旦 超过 B 个就把开一个新的块并将 x 作为省会，然后不断弹出 Sta 中加入这个省的元素，并继续枚举 v。

  2. 处理完所有子树后，将 x 也加入到集合 Sta 中，此时在 Sta 中的节点将被返回到上一层，显然 Sta 的大小最大为 B−1 个子树节点（大于等于 B 时会拆出一个新的省） + x 本身，即 Sta 中结点不超过 B 个。

  3. 在 dfs 结束后可能还剩下 不超过 B 个点，并入以根为省会的省份中。

合法性说明：

对于每个结点，它向上传回去的结点不超过 B 个，所以对于一个子树会对集合最多增加 B-1 个节点，那么每个块的大小最大为 2B−1，满足条件。

在 dfs 结束后，栈中最多有 B 个结点，所以把这 B 个节点并入以根节点为省会的省中，那么此时根节点这个块的大小最大可能为 3B−1 ，方法成立。

时间复杂度显然是 O(n) 的（就跑一遍 dfs ，快得飞起）。 虽然我也不知道为什么 n,m \le 2000 。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=2005;

struct Edge{
    int vet,nxt;
}e[N<<1];

int n,B,Top=0,cnt=0,edge=0,head[N];
int sta[N],Belong[N],Root[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void addedge(int x,int y){
    e[++edge].vet=y;
    e[edge].nxt=head[x];
    head[x]=edge;
}

inline void dfs(int x,int fa){
    int rec=Top;        //记录栈此时的状态，类似的思想可以在可撤销并查集中见到（可能吧）
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (v==fa) continue;
        dfs(v,x);
        if (Top-rec>=B){        //如果超过 B 个
            Root[++cnt]=x;
            while (Top!=rec)    //把超过部分的结点统计到新的省份中
                Belong[sta[Top--]]=cnt;
        }
    }
    sta[++Top]=x;       //把当前节点 x 放入栈中
}

int main(){
    //freopen("Luogu2325.in","r",stdin);
    //freopen("Luogu2325.out","w",stdout);
    n=read(),B=read();
    for (int i=1;i<=n-1;i++){
        int x=read(),y=read();
        addedge(x,y);
        addedge(y,x);
    }
    dfs(1,0);
    if (cnt==0) Root[++cnt]=1;      //特判，如果一个省份都没有创建，那么以 1 为省会创建一个省份。
    while (Top!=0) Belong[sta[Top--]]=cnt;      //把剩余结点放到 1 为省会的省份中
    printf("%d\n",cnt);
    for (int i=1;i<=n;i++)
        printf("%d ",Belong[i]);
    printf("\n");
    for (int i=1;i<=cnt;i++)
        printf("%d ",Root[i]);
    printf("\n");
    return 0;
}