做法是dfs整棵树,当访问一个点\(x\)时,先访问儿子,若某个时刻子树大小\(\ge b\)时,就把那些点放在一个省里,省会记为\(x\),访问完儿子再把\(x\)加入栈.最后栈中剩余的没加入任何省的点加入最后一个省
(这就叫做树分块)
正确性的话,首先前面的省大小\(\le 2b\),然后在最后栈中剩余的点\(\le b\),所以一个省最多\(3b\)个点
有人说树分块没什么用 不过好像除了这题和树上莫队确实没什么用
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
using namespace std;
const int N=5000+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],tot=1;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot;
}
int n,b,ff[N],sh[N],m;
int st[N],tp;
void dfs(int x,int ffa)
{
int la=tp;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==ffa) continue;
dfs(y,x);
if(tp-la>=b)
{
sh[++m]=x;
while(tp!=la) ff[st[tp--]]=m;
}
}
st[++tp]=x;
}
int main()
{
n=rd(),b=rd();
for(int i=1;i<n;++i) add(rd(),rd());
for(int i=1;i<=n;++i) ff[n+i]=n+i;
dfs(1,0);
while(tp) ff[st[tp--]]=m;
printf("%d\n",m);
for(int i=1;i<=n;++i) printf("%d ",ff[i]);putchar('\n');
for(int i=1;i<=m;++i) printf("%d ",sh[i]);
return 0;
}