bzoj 1086[SCOI2005]王室联邦

1086: [SCOI2005]王室联邦

Time Limit: 10 Sec Memory Limit: 162 MBSec Special Judge

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define LL long long 
 6 
 7 using namespace std;
 8 
 9 const int MAXN = 1e3 + 10;
10 
11 int top = 0;
12 int N;
13 int B;
14 int root[MAXN];
15 int bel[MAXN];
16 int vis[MAXN];
17 int head[MAXN];
18 int s[MAXN];
19 
20 int cnt = 0;
21 
22 struct edge {
23     int u, v;
24     int next;
25 } g[MAXN * 10];
26 
27 void addedge(int u, int v)
28 {
29     g[++cnt].v = v;
30     g[cnt].next = head[u];
31     head[u] = cnt;
32 }
33 
34 inline LL read()
35 {
36     LL x = 0, w = 1; char ch = 0;
37     while(ch < '0' || ch > '9') {
38         if(ch == '-') {
39             w = -1;
40         }
41         ch = getchar();
42     }
43     while(ch >= '0' && ch <= '9') {
44         x = x * 10 + ch - '0';
45         ch = getchar();
46     }
47     return x * w;
48 }
49 
50 void DFS(int x)
51 {
52     vis[x] = 1;
53     int bottom = top - 1;
54     for(int j = head[x]; j; j = g[j].next) {
55         int to = g[j].v;
56         if(!vis[to]) {
57             DFS(to);
58             if(top - bottom - 1 >= B) {
59                 //cout<<cnt<<" "<<bottom<<" "<<top<<endl; 
60                 root[++cnt] = x;
61                 while(top > bottom + 1) {
62                     bel[s[top - 1]] = cnt;
63                     top--;    
64                 }
65             }
66         }
67     }
68     s[top++] = x;
69 }
70 
71 int main()
72 {
73     N = read(), B = read();
74     for(int i = 1; i < N; i++) {
75         int u = read(), v = read();
76         addedge(u, v);
77         addedge(v, u);
78     }
79     cnt = 0;
80     DFS(1);
81     while(top) {
82         bel[s[top - 1]] = cnt;
83         top--;
84     }
85     printf("%d
", cnt);
86     for(int i = 1; i <= N; i++) {
87         printf("%d ", bel[i]);
88     }
89     printf("
");
90     for(int i = 1; i <= cnt; i++) {
91         printf("%d ", root[i]);
92     }
93     return 0;
94 }

View Code