BZOJ1086 [SCOI2005]王室联邦 【树分块】

tonyfang posted @ 2015年8月29日 17:44 in BZOJ with tags c++ OI , 508 阅读

树分块,在常州的时候$wrh$和我们讲过。

这题是个模板题。

参考$PoPoQQQ$大神,写的代码。

实现起来并不那么困难。

 

//bzoj1086
# include <stdio.h>
using namespace std;

int head[1010],next[2020],to[2020],tot=0;
int c[1010],root[1010],s[10001],top,cnt;
inline void add(int u,int v) {to[++tot]=v;next[tot]=head[u];head[u]=tot;}
int n,b;
void g(int x,int from) {
	int bottom=top;
	for(int i=head[x];i;i=next[i]) {
		if(to[i]!=from) {
			g(to[i],x);
			if(top-bottom>=b) {
				root[++cnt]=x;
				while(top!=bottom)
					c[s[top--]]=cnt;
			}
		}
	}
	s[++top]=x;
}
int main() {
	scanf("%d%d",&n,&b);
	for (int i=1,u,v;i<=n-1;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
	g(1,0);
	while(top)c[s[top--]]=cnt;
	printf("%d\n",cnt);
	for (int i=1;i<=n;++i)printf("%d ",c[i]);printf("\n");
	for (int i=1;i<=cnt;++i)printf("%d ",root[i]);printf("\n");
	return 0;
}
हिन्दी-सवाल-पत्रों.c 说:
2023年4月25日 21:35

Hindi Model Question Papers Bihar School 10th Exam Board BSEB, Bihar Board 10th Class Model Papers 2023 Matric Exam Pattern, BSEB Patna Board Matric 10th Model Papers 2023 Sample Questions, Bihar Board 10th Model Papers 2023 Download, हिन्दी-सवाल-पत्रों.com BSEB Matric Bihar matric model paper 2023 bseb 10th sample paper 2023, bihar board 10th model paper 2023 pdf, bihar board 10th class model test paper 2023, bseb matric previous sample paper class 10th bihar board model question paper, bseb matric model question paper 2023.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter