danihao123's Blog

最近想捉一下树分块，这道题肯定是要做的啦~

这个题的方法就是蜜汁贪心，在其他树分块的题目中也有应用。

代码：

/**************************************************************
    Problem: 1086
    User: danihao123
    Language: C++
    Result: Accepted
    Time:16 ms
    Memory:880 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
using std::stack;
const int maxn=1005;
const int maxm=maxn*2;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
  graph_cnt++;
  next[graph_cnt]=first[u];
  first[u]=graph_cnt;
  to[graph_cnt]=v;
}
 
int belong[maxn],cap[maxn];
int block_cnt=0;
stack<int> S;
int B;
void DFS(int u,int fa){
  int siz=S.size();
  for(int i=first[u];i;i=next[i]){
    int v=to[i];
    if(v==fa){
      continue;
    }
    DFS(v,u);
    if((S.size()-siz)>=B){
      block_cnt++;
      cap[block_cnt]=u;
      while(S.size()>siz){
        int x=S.top();S.pop();
        belong[x]=block_cnt;
      }
    }
  }
  S.push(u);
}
int main(){
  register int i;
  bool OK;
  int n,u,v;
  scanf("%d%d",&n,&B);
  for(i=1;i<=(n-1);i++){
    scanf("%d%d",&u,&v);
    AddEdge(u,v);
    AddEdge(v,u);
  }
  if(n<B){
    puts("0");
    return 0;
  }
  DFS(1,0);
  while(!S.empty()){
    int x=S.top();S.pop();
    belong[x]=block_cnt;
  }
  printf("%d\n",block_cnt);
  OK=false;
  for(i=1;i<=n;i++){
    if(OK){
      putchar(' ');
    }
    OK=true;
    printf("%d",belong[i]);
  }
  putchar('\n');
  OK=false;
  for(i=1;i<=block_cnt;i++){
    if(OK){
      putchar(' ');
    }
    OK=true;
    printf("%d",cap[i]);
  }
  putchar('\n');
  return 0;
}