题意：n个点的树，要求分块，使得每一块的大小在[b, 3b]内且块与某个点形成的块是连通的（某个点既可以是块内也可以在块外）（n<=1000, b<=n）

#include 
     
      using namespace std;const int N=1005;int ihead[N], cnt, s[N], top, p[N], root[N], num, b, n;struct E { int next, to; }e[N<<1];void add(int x, int y) { e[++cnt]=(E){ihead[x], y}; ihead[x]=cnt; e[++cnt]=(E){ihead[y], x}; ihead[y]=cnt; }void dfs(int x, int f) {	int last=top;	for(int i=ihead[x]; i; i=e[i].next) if(e[i].to!=f) {		dfs(e[i].to, x);		if(top-last>=b) { ++num; root[num]=x; while(top!=last) p[s[top--]]=num; }	}	s[++top]=x;}int main() {	scanf("%d%d", &n, &b);	for(int i=0; i
      
       >1, 0);	while(top) p[s[top--]]=num;	printf("%d\n", num);	for(int i=1; i<=n; ++i) printf("%d ", p[i]); puts("");	for(int i=1; i<=num; ++i) printf("%d ", root[i]);	return 0;}
      
     

　　

块状树系列= =首先教你如何分块树= =

唯一不同的是这题并不是让你真正的分块树使得每个块都是连通的，而是加了一个附加点使得块连通。

膜拜了vfk和popoqqq神犇们的题解后自行yy了一下，发现其实是这样的= =：

首先我们可以用某种策略：对于当前点x，一棵棵遍历子树。子树给我传回一个个数小于b的与我连通的“连通块”。如果当我获得的连通块大小>=b时（此时一定<=2b），将这些个连通块合并成一个块，“某个点”就是当前点。最后我向自己的父亲也返回一个小于等于b的“连通块”（当然现在加上自己了所以整个块连通）。当然你会问，最后根得到的连通块如果<b怎么办！不符合题意啊！妈呀仔细想想啊= =随便找一个点合并就行了啊= =因为你之前合并的所有块大小都是<=2b的啊= =这就是题目给的3b的由来= =

对于维护所谓的“连通块”，用一个分割的栈即可= =