Luogu2325 [SCOI2005] 王室联邦(树上分块)题解

发布于 2021-01-05  490 次阅读


本文同步发表至我的洛谷博客
原题面

题意:

把一个有 $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){
            Root[++cnt]=x;
            while (Top!=rec)
                Belong[sta[Top--]]=cnt;
        }
    }
    sta[++Top]=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;
    while (Top!=0) Belong[sta[Top--]]=cnt;
    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;
}

我们无法选择过去,但我们可以改变未来。