将一棵树划分为若干块,每个块未必连通,但并上这个块的中心后连通,中心可以不是块内的点,每个块的大小 (in [B,3B])
Solution
经典的王室联邦分块法
DFS 整棵树,对于每个子树,将其中能分块的结点分块,不能分块的结点以集合的形式上传,和上一层一起分块
最后多余下来的一些点并入最后一个块中
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int n,b,c[N],x[N],vis[N],ind,t1,t2;
vector <int> g[N];
set<int> dfs(int p) {
set<int> res;
vis[p]=1;
for(int q:g[p]) {
if(vis[q]) continue;
set<int> tmp=dfs(q);
for(int t:tmp) res.insert(t);
if(res.size()>=b) {
++ind;
x[ind]=p;
for(int t:res) c[t]=ind;
res.clear();
}
}
res.insert(p);
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin>>n>>b;
for(int i=1;i<n;i++) {
cin>>t1>>t2;
g[t1].push_back(t2);
g[t2].push_back(t1);
}
set<int> res = dfs(1);
if(ind==0) ++ind;
for(int t:res) c[t]=ind;
cout<<ind<<endl;
for(int i=1;i<=n;i++) cout<<c[i]<<" ";
cout<<endl;
for(int i=1;i<=ind;i++) cout<<x[i]<<" ";
cout<<endl;
}