bzoj 1086 王室联邦 (dfs，构造)

本文主要是介绍bzoj 1086 王室联邦 (dfs，构造)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

思路：

     首先我们dfs，如果一个节点v的儿子u所在的子树大于等于B，那么就把这个子树当作一个省份，对于这种情况，省会是u,v其实都可以。如果一个儿子u所在的子树小于B，可以先暂存起来，继续遍历其他儿子，当暂存的数量大于等于B的时候，将暂存的都归为一个省，省会为v，因为会暂存的子树大小为B-1,所以这样产生的子树大小最大为2B-2，在处理完所有子树，就把v也加入到暂存的地方返回去，这里能看出，一个栈很适合处理这个过程。
    这样一路处理下来，只剩下一个问题，最后，我可能还剩下一个包含根节点的最大B-1个节点的暂存节点。因为我们之前说子树最大为2B-2，所以直接把剩下的暂存节点归到上一个省份里面即可（记得改省会）
    我们可以注意到，我们这样的分块其实只能保证块大小，不能保证连通性

错误及反思：

有人说是树上莫队前置题目，主要是为了理解树上分块的大致思路。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
vector<int> son[N];
int n,b;
int ans[N],sh[N],tot=1;
stack<int> s;
void dfs(int now,int fa){int si=s.size();for(int i=0;i<son[now].size();i++){if(son[now][i]!=fa){dfs(son[now][i],now);//if(now==6) printf("#%d\n",s.size()-si);if(s.size()-si>=b){while(s.size()!=si){ans[s.top()]=tot;s.pop();}sh[tot++]=now;}}}s.push(now);
}
int main(){scanf("%d%d",&n,&b);for(int i=0;i<n-1;i++){int ta,tb;scanf("%d%d",&ta,&tb);son[ta].push_back(tb);son[tb].push_back(ta);}dfs(1,1);while(!s.empty()){ans[s.top()]=tot-1;s.pop();}sh[tot-1]=1;tot--;printf("%d\n",tot);for(int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");for(int i=1;i<=tot;i++) printf("%d ",sh[i]);
}