【BZOJ1086】【SCOI2005】王室联邦 树分块

题解：思想上是深搜+栈，每当栈中元素达到b个，就分成一个块。

然后最后会剩下部分，分到最后一个块中。

其实我认为开始的所有块都是b个啊，然后最后一个块是b+若干个，不会超过2b。

不是很理解2b~3b这个概念。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1010
using namespace std;
struct KSD
{
	int v,next;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v)
{
	e[++cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int n,m;
int id[N],root[N],group;
// 属于哪个块，块的“省会”，总共几个块
int stk[N],top;
void dfs(int x,int p)
{
	int i,v,temp=top;
	for(i=head[x];i;i=e[i].next)
	{
		v=e[i].v;
		if(v==p)continue;
		dfs(v,x);
		if(top-temp>=m) // 树分块判定
		{
			root[++group]=x;
			while(top!=temp)id[stk[top--]]=group;
		}
	}
	stk[++top]=x;
}
int main()
{
	freopen("test.in","r",stdin);
	int i,a,b;
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
	dfs(1,0);
	while(top)id[stk[top--]]=group; 
	//剩下的多出来一点扔到最后一个块里来保证>=B
	printf("%d\n",group);
	for(i=1;i<=n;i++)printf("%d ",id[i]);
	puts("");
	for(i=1;i<=group;i++)printf("%d ",root[i]);
}

【BZOJ1086】【SCOI2005】王室联邦 树分块

原文：http://blog.csdn.net/vmurder/article/details/42803451