【树分块】王室联邦

分块

传送门：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;
}