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

2019-11-06 06:26:50

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

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

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 1005int 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]);}

上一篇：通过反汇编定位段错误

下一篇：数组解简单多次递归