Description
“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成
员来管理。他的国家有n个城市，编号为1..n。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条
直接或间接的道路。为了防止管理太过分散，每个省至少要有B个城市，为了能有效的管理，每个省最多只有3B个
城市。每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经
过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。一个城市可以作为多个省的省会。聪明的
你快帮帮这个国王吧！
Solution
获得成就“发现了一道大水题”
嗯 据说这是一种非常科学的分块法
dfs，加入一个子树后如果大小已经大于等于s就分一块
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> using namespace std; int n,b,head[1001],cnt=0,stack[1001],block[1001],capital[1001],num=0,top=0; struct Node { int next,to; }Edges[2002]; void addedge(int u,int v) { Edges[++cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v; } void dfs(int u,int f) { int now=top; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(f==v)continue; dfs(v,u); if(top-now>=b) { capital[++num]=u; while(top!=now)block[stack[top--]]=num; } } stack[++top]=u; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&b); for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(1,0); while(top)block[stack[top--]]=num; printf("%d ",num); for(int i=1;i<=n;i++) printf("%d ",block[i]); printf(" "); for(int i=1;i<=num;i++) printf("%d ",capital[i]); return 0; }