传送门

做法是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;

}