题目大意：给定一棵树，要求将这棵树分成一些块，使每块大小在[B,3B]之间
《手把手教你块状树系列》
- -终于搞懂这题怎么做了
- -去网上扒了个代码居然是错的 坑死我了
- -还好题解的思想是对的
朴素的分块方式是贪心 能加就加 这种方法存在着严重的效率问题 可以被菊花卡成O(n)块
因此我们可以为其它的块预留位置 如果一块大小刚好>=b 就将这坨东西分成一块
首先任选一点开始深搜 维护一个栈 每个点退出递归时压栈 自下至上进行合并
如果某棵子树深搜完之后栈内元素数>=b 就把当前的栈内元素合并为一个块
但是这种方法存在一个问题 就是如果某棵子树深搜之后不到b 去深搜下一个子树 可能在下一个子树内部的某个位置超过b
这样会导致分成的块不连通
因此我们在每次进入递归时维护一个栈底，对于当前子树来说这个栈底就是整个栈的底，栈底以下的元素不能修改或弹栈
这样当一棵子树深搜过后由于子树内未分块节点不超过b，之前搜过的未分块节点数也不超过b，因此每块不超过2b
那么题目为什么给了3b呢？
深搜结束后可能会剩余一些节点，这些节点的数量不超过b，而且一定与当前分出的最后一块连通
因此我们将剩余节点分到最后一块中，可以保证最后一块的大小不超过3b
一遍深搜即可出解。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 1010
using namespace std;
struct abcd{
int to,next;
}table[M<<1];
int head[M],tot;
int n,b,cnt;
int belong[M],root[M],stack[M],top;
void Add(int x,int y)
{
table[++tot].to=y;
table[tot].next=head[x];
head[x]=tot;
}
void DFS(int x,int from)
{
int i,bottom=top;
for(i=head[x];i;i=table[i].next)
if(table[i].to!=from)
{
DFS(table[i].to,x);
if(top-bottom>=b)
{
root[++cnt]=x;
while(top!=bottom)
belong[stack[top--]]=cnt;
}
}
stack[++top]=x;
}
int main()
{
int i,x,y;
cin>>n>>b;
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
Add(x,y);Add(y,x);
}
DFS(1,0);
while(top)
belong[stack[top--]]=cnt;
cout<<cnt<<endl;
for(i=1;i<=n;i++)
printf("%d%c",belong[i],i==n?'\n':' ');
for(i=1;i<=cnt;i++)
printf("%d%c",root[i],i==cnt?'\n':' ');
return 0;
}