[BZOJ1086][SCOI2005]王室联邦（树上分块）

题目描述

传送门

题解

http://blog.****.net/popoQQq/article/details/42772237

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 1005 int n,b,x,y,cnt; int stack[N],top,belong[N],root[N]; int tot,point[N],nxt[N*2],v[N*2]; void add(int x,int y) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; } void dfs(int x,int fa) { int bottom=top; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) { dfs(v[i],x); if (top-bottom>=b) { root[++cnt]=x; while (top!=bottom) belong[stack[top--]]=cnt; } } stack[++top]=x; } int main() { scanf("%d%d",&n,&b); for (int 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; PRintf("%d\n",cnt); for (int i=1;i<=n;++i) printf("%d%c",belong[i]," \n"[i==n]); for (int i=1;i<=cnt;++i) printf("%d%c",root[i]," \n"[i==cnt]); }