285484026

【SCOI 2005】王室联邦 树上分块?
在WZH大神(PS:我是渣渣WZH)的博客看见的一个分块题目,刚好要复习分块,于是我就研究了一下树上分块,恩,这个...
扫描右侧二维码阅读全文
01
2018/10

【SCOI 2005】王室联邦 树上分块?

在WZH大神(PS:我是渣渣WZH)的博客看见的一个分块题目,刚好要复习分块,于是我就研究了一下树上分块,恩,这个题目的要求和树上分块差不多。没什么就是原来的SIZE变成题目规定的B了,然后这就变成了分块的模板题目。

BZOJ
大神WZH的博客ORZWZH

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 

题解:
构造树上分块的原理是深搜,我们搜索每一个子树如果我们子树的大小已经大于B,那么我们就把到我现在这个点为止的所有加入当前块中,然后把我这个点设置为省会。

若到根节点的大小都小于B,那么我就把根节点加入最近的分块,最近的分块一定和根节点没有加入分块联通。因为我们前面的每个分块大小一定大于B,小于2B,所以加上我们这个点附近的点之后我们这个分块一共只有不大于3B个点。

哦,还要说一下为了防止不同的子树(不通过省会连通)放在同一个分块中那么,我们要记录一下我的当前点在栈的位置。最多只能将这个点以前的点加入分块。

代码:

#include <iostream>
#include <cstdio>

const int MAXN = 10050;

using namespace std;

int N,B,e = 1,top,sz;
int head[MAXN],s[MAXN],BL[MAXN],RT[MAXN];

struct node{
    int v,next;
}edge[MAXN];

inline int read()
{
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&&ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

inline void addedge(int u,int v){
    edge[e] = (node){v,head[u]};head[u] = e++;
}

inline void init()
{
    N = read();B = read();
    
    int u,v;
    
    for(int i = 1;i < N;i++){
        u = read();v = read();
        addedge(u,v);addedge(v,u);
    }
    
}

void dfs(int u,int fa){
    int tmp = top;        //tmp 是当前栈的位置 
    
    for(int i = head[u];i;i = edge[i].next){
        int v = edge[i].v;
        if(v != fa){
            dfs(v,u);
            
            if(top - tmp >= B){
                RT[++sz] = u;
                while(top != tmp) BL[s[top--]] = sz;
            } 
        }
    }
    
    s[++top] = u;
}

int main()
{
    init();
    
    dfs(1,0);
    
    while(top) BL[s[top--]] = sz;
    printf("%d\n",sz);
    for(int i = 1;i <= N;i++) printf("%d ",BL[i]);
    printf("\n");
    for(int i = 1;i <= sz;i++) printf("%d ",RT[i]);
    return 0;
} 
Last modification:October 1st, 2018 at 08:07 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment