数据结构：树上分块

把所谓的树结构分成一块儿一块儿的？

当然这种数据结构并不强力，如果想要借助其分块儿的思想来解决问题，肯定有更好的其它的算法来替代它

所以，这里只是铺一个知识点探探路而已

典型例题BZOJ1086

题意就是把树分块儿

但是为何样例是错的？

其实递归的学问还是很大的

 1 #include<cstdio>
 2 const int maxn=1005;
 3 const int maxm=2005;
 4 int n,B,cnt,top,pro;
 5 int g[maxn],q[maxn],cap[maxn],belong[maxn],size[maxn];
 6 struct Data
 7 {
 8     int t,next;
 9 }e[maxm];
10 inline int read()
11 {
12     int x=0,f=1;char ch=getchar();
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 void insert(int u,int v)
18 {
19     e[++cnt].t=v;e[cnt].next=g[u];g[u]=cnt;
20     e[++cnt].t=u;e[cnt].next=g[v];g[v]=cnt;
21 }
22 void dfs(int x,int fa)
23 {
24     q[++top]=x;
25     for(int tmp=g[x];tmp;tmp=e[tmp].next)
26     {
27         if(e[tmp].t!=fa)
28         {
29             dfs(e[tmp].t,x);
30             size[x]+=size[e[tmp].t];  //退栈时更新size 
31             if(size[x]>=B)  //如果可以分块儿了 
32             {
33                 size[x]=0;
34                 cap[++pro]=x;  //当前x作为省会 
35                 while(q[top]!=x) belong[q[top--]]=pro;  //弹出来带上连通分量标记 
36             }
37         }
38     }
39     size[x]++;//自己 
40 }
41 void paint(int x,int fa,int c)
42 {
43     if(belong[x]) c=belong[x];
44     else belong[x]=c;
45     for(int tmp=g[x];tmp;tmp=e[tmp].next)
46         if(e[tmp].t!=fa) paint(e[tmp].t,x,c);
47 }
48 int main()
49 {
50     int u,v;
51     n=read();B=read();
52     if(n<B) {puts("0");return 0;}
53     for(int i=1;i<n;i++)
54     {
55         u=read();v=read();
56         insert(u,v);
57     }
58     dfs(1,0);  //子树大小超过B直接划省，根为省会 
59     if(pro==0) cap[++pro]=1;
60     paint(1,0,pro); 
61     printf("%d
",pro);
62     for(int i=1;i<=n;i++) printf("%d ",belong[i]);
63     puts("");
64     for(int i=1;i<=pro;i++) printf("%d ",cap[i]);
65     puts("");
66     return 0;
67 }