BZOJ 1086 王室联邦

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

http://www.lydsy.com/JudgeOnline/problem.php?id=1086

思路:贪心，每次当储存的儿子大于等于B时，分出一个块，这样每次每个块至多为2B，这样剩下的没有被分的块小于B，可以加入任意一个块，都是合法的。

 #include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 int tot,go[],first[],next[],n,m;

 int top,c[],pd,size[],cap[],belong[],sz;

 int read(){

     char ch=getchar();int t=,f=;

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void insert(int x,int y){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

 }

 void add(int x,int y){

     insert(x,y);insert(y,x);

 }

 void dfs(int x,int fa){

     c[++top]=x;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (pur==fa) continue;

         dfs(pur,x);

         if (size[x]+size[pur]>=m){

             cap[++sz]=x;size[x]=;

             while (c[top]!=x) belong[c[top--]]=sz;

         }else size[x]+=size[pur];

     }

     size[x]++;

 }

 void find(int x,int fa){

     if (belong[x]) {

         pd=belong[x];

         return;

     }

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (pur==fa) continue;

         if (!pd) find(pur,x);

     }

 }

 int main(){

     n=read();m=read();

     if (n<m){

         printf("0\n");

         return ;

     }

     if (m==){

         printf("%d\n",n);

         for (int i=;i<=n;i++)

          printf("%d ",i);

         printf("\n");

         for (int i=;i<=n;i++)

          printf("%d ",i);

         printf("\n");

         return ;

     }

     for (int i=;i<n;i++){

         int x=read(),y=read();

         add(x,y);

     }

     dfs(,);

     pd=;

     int cnt=,th;

     for (int i=;i<=n;i++)

      if (!belong[i]) cnt++,th=;

     if (cnt>=m){

         sz++;

         cap[sz]=th;

         for (int i=;i<=n;i++)

          if (!belong[i]) belong[i]=sz;

     }

     for (int i=;i<=n;i++)

       if (!belong[i]){

          if (!pd) find(i,);

          if (pd) belong[i]=pd;

     }

     printf("%d\n",sz);

     for (int i=;i<=n;i++)

      printf("%d ",belong[i]);

     printf("\n");

     for (int i=;i<=sz;i++)

      printf("%d ",cap[i]);

     printf("\n");

 }