|
将一棵树维护成若干个满足条件(块内点数在[B，3B]之间)的联通块，开一个dfs栈维护联通快，可知，dfs栈中的所有点必然联通，假设一棵子树的根节点x在栈内是第i个，那么在遍历它的子树时，若top-i>=b，则将这一段作为一个联通块，将它们的信息维护好(省会直接选根)再出栈。这样可以保证这样处理出来的联通块大小在[B,2*B）之间，然后最后dfs完剩下的那一块在栈内的大小必然在[0,B）之间，那么直接将这一块加到最后一块里就好了。
/**************************************************************
Problem: 1086
User: syh0313
Language: C++
Result: Accepted
Time:28 ms
Memory:1348 kb
****************************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int maxn=2010;
int n,b,num[maxn],cap[maxn],cnt,sta[maxn],stanum[maxn],top;
int topt,st[maxn],nt[maxn],to[maxn];
void add(int x,int y)
{to[++topt]=y; nt[topt]=st[x]; st[x]=topt;}
void dfs(int x,int fa)
{
sta[++top]=x; stanum[x]=top;
int p=st[x];
while (p)
{
if (to[p]!=fa)
{
dfs(to[p],x);
if (top-stanum[x]>=b)
{
cap[++cnt]=x;
while (top>stanum[x])
{
num[sta[top--]]=cnt;
}
}
}
p=nt[p];
}
}
int main()
{
scanf("%d%d",&n,&b);
for (int i=1;i<n;i++)
{
int xx,yy; scanf("%d%d",&xx,&yy);
add(xx,yy); add(yy,xx);
}
dfs(1,0);
for (int i=1;i<=n;i++) if (!num[i]) num[i]=cnt;
printf("%d\n",cnt);
for (int i=1;i<=n;i++) printf("%d ",num[i]);
puts("");
for (int i=1;i<=cnt;i++) printf("%d ",cap[i]);
return 0;
}
| 
转播
