【树分块】王室联邦

传送门:BZOJ1086

SCOI2005


思路:用一个栈维护当前节点子树中未被划分的节点个数,如果超过了块的大小就分掉,最后剩下的划分到上一块。

注意:子树大小不是栈内元素个数。


代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 3000
int n,m,cnt,tot,top,x,y,belong[N],stk[N],ans[N],head[N];
struct edge{int v,nxt;}e[N];
void add(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void dfs(int u,int fa){
int now=top;
for (int i=head[u];i;i=e[i].nxt){
int v=e[i].v; if (v==fa) continue;
dfs(v,u);
if (top-now>=m){ans[++cnt]=u; for (;top-now;top--) belong[stk[top]]=cnt;}
//------子树大小为top-now
}
stk[++top]=u;
}
int main(){
scanf("%d%d",&n,&m);
if (n<m){puts("0"); return 0;}
for (int i=1;i<n;i++){scanf("%d%d",&x,&y); add(x,y); add(y,x);}
dfs(1,0);
for (;top;top--) belong[stk[top]]=cnt;//多余节点划分到上一个块
printf("%d\n",cnt);
for (int i=1;i<=n;i++) printf("%d ",belong[i]); puts("");
for (int i=1;i<=cnt;i++) printf("%d ",ans[i]); puts("");
return 0;
}