【题意】给定n个点的树，要求划分成若干大小为[B,3B]的块，满足一个块加上一个核心点后连通，求方案。n<=1000。

【算法】树分块

【题解】参考： 讲得很详细了，就不必听我口胡了。。。

树分块算法的起源？用这道题的树分块算法可以实现将一棵树划分成若干[B,3B]的块。

DFS过程中用栈记录，扫描到点x时记录top作为当前子树x的栈底（下面的点不能取）。

如果某棵子树扫描后有>=B个点，那么直接构成一块。

如果两棵子树扫描后才有>=B个点，那么这一块一定在[B,2B)之间，也构成一块。

最后剩余的点加入最后一块，至多会使最后一块变成3B。

复杂度O(n)。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=1010;int n,B,first[maxn],s[maxn],st[maxn],belong[maxn],tot=0,cnt=0,ans=0,top=0;struct edge{
    int v,from;}e[maxn*2];void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void dfs(int x,int fa){    int lim=top;    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){        dfs(e[i].v,x);        if(top-lim>=B){            ans++;s[ans]=x;            while(top>lim)belong[st[top--]]=ans;        }    }    st[++top]=x;}int main(){    scanf("%d%d",&n,&B);    for(int i=1;i