BZOJ1086 王室联邦（树上分块）

今天药忘吃喽~ 2021-12-03 06:34 196阅读 0赞

## 题意： ##

## 1086: \[SCOI2005\]王室联邦 ##

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge  
Submit: 1094  Solved: 650  
\[[Submit][]\]\[[Status][]\]\[[Discuss][]\]

## Description ##

“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成  
员来管理。他的国家有n个城市，编号为1..n。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条  
直接或间接的道路。为了防止管理太过分散，每个省至少要有B个城市，为了能有效的管理，每个省最多只有3B个  
城市。每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经  
过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。一个城市可以作为多个省的省会。聪明的  
你快帮帮这个国王吧！

## Input ##

第一行包含两个数N，B（1<=N<=1000, 1 <= B <= N）。接下来N－1行，每行描述一条边，包含两个数，即这  
条边连接的两个城市的编号。

## Output ##

如果无法满足国王的要求，输出0。否则输出数K，表示你给出的划分方案中省的个数，编号为1..K。第二行输  
出N个数，第I个数表示编号为I的城市属于的省的编号，第三行输出K个数，表示这K个省的省会的城市编号，如果  
有多种方案，你可以输出任意一种。

## Sample Input ##

8 2   
1 2   
2 3   
1 8   
8 7   
8 6   
4 6   
6 5

## Sample Output ##

3   
2 1 1 3 3 3 3 2   
2 1 8

## 分析：裸分块，会dfs就行了，对树上将点进行分块，每一块的大小都为B到3B。要使每一块的大小均为B至3B，只需要开一个栈，在我们遍历每一个点时搜寻它目前在栈中的子树大小，如果大于B，我们就将他以及他的儿子放在一个块里，并且这个点就是该题中的省会。   在我们dfs完之后，还会剩下一些点，这些点肯定少于B个，所以我们将他归入最后一个分块即可。参考[https://blog.csdn.net/stevensonson/article/details/79786490][https_blog.csdn.net_stevensonson_article_details_79786490]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e4+5;
    int head[N],nxt[N],col[N],n,b,cnt,rec,top,root[N],sta[N];
    struct node{
        int to,val;
    }L[N];
    void add(int x,int y){
        L[cnt]=(node){y,1};
        nxt[cnt]=head[x];head[x]=cnt;cnt++;
        L[cnt]=(node){x,1};
        nxt[cnt]=head[y];head[y]=cnt;cnt++;
    }
    void dfs(int x,int fa){
        int now=top;
        for(int i=head[x];i!=-1;i=nxt[i]){
            int to=L[i].to;
            if(to==fa) continue;
            dfs(to,x);
            if(top-now>=b){root[++rec]=x;while(top!=now)col[sta[top--]]=rec;}
        }
        sta[++top]=x;
    }
    int main(){
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&b);
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        dfs(1,0);
        while(top) col[sta[top--]]=rec;
        printf("%d\n",rec);
        for(int i=1;i<=n;i++) printf("%d ",col[i]);printf("\n");
        for(int i=1;i<=rec;i++) printf("%d ",root[i]);
        return 0;
    }

[Submit]: http://www.lydsy.com/JudgeOnline/submitpage.php?id=1086
[Status]: http://www.lydsy.com/JudgeOnline/problemstatus.php?id=1086
[Discuss]: http://www.lydsy.com/JudgeOnline/bbs.php?id=1086
[https_blog.csdn.net_stevensonson_article_details_79786490]: https://blog.csdn.net/stevensonson/article/details/79786490