[bzoj1086]王室联邦
树分块裸题。。。(学树上莫队前提条件之一)
http://blog.csdn.net/wzq_qwq/article/details/47297885
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdlib> 5 #include <map> 6 #include <string> 7 #include <vector> 8 #include <stack> 9 #include <cmath> 10 #include <queue> 11 #include <cstdio> 12 #include <set> 13 using namespace std; 14 15 const int N=10000; 16 17 int tot=1,head[N],rest[N],to[N]; 18 void add(int u,int v){ 19 tot++; 20 to[tot]=v; 21 rest[tot]=head[u]; 22 head[u]=tot; 23 } 24 int n,b; 25 int st[N],p,bel[N],root[N],v[N],cnt; 26 void dfs(int x){ 27 v[x]=1; 28 int bot=p; 29 for(int i=head[x];i;i=rest[i]){ 30 int t=to[i]; 31 if(!v[t]){ 32 dfs(t); 33 if(p-bot>=b){ 34 root[++cnt]=x; 35 do 36 bel[st[p--]]=cnt; 37 while(p!=bot); 38 } 39 } 40 } 41 st[++p]=x; 42 } 43 int main(){ 44 scanf("%d%d",&n,&b); 45 for(int i=1;i<n;i++){ 46 int u,v; 47 scanf("%d%d",&u,&v); 48 add(u,v); 49 add(v,u); 50 } 51 dfs(1); 52 while(p)bel[st[p--]]=cnt; 53 printf("%d\n",cnt); 54 for(int i=1;i<n;i++)printf("%d ",bel[i]); 55 printf("%d\n",bel[n]); 56 for(int i=1;i<cnt;i++)printf("%d ",root[i]); 57 printf("%d\n",root[cnt]); 58 }View Code 优质内容筛选与推荐>>