C 题解_牛客博客

经典的王室联邦题目 .

考虑先划分子树 , 然后递归处理问题 . 当子树比较小的时候 , 可能不足 $B$ 个 , 所以要维护以每个节点为根的目前没有处理的连通块 . 显然这样的块大小 $< B$ .

考虑对于 $u$ 的几个儿子 $v_1,v_2,\dots,v_k$ , 如果几个合并起来的大小合适 , 那么可以把 $u$ 设为省会 . 那么不断加 , 直到超过 $B$ , 此时就可以处理这几个块 . 最后可能会有剩下的 , 如果还不能和最顶端的 $u$ 凑成一起 , 那么就把他们当做 $u$ 为根的剩余未处理的部分 .

这样每个块的大小最多为 $2 B - 1$ . 最后可能还剩下以 $1$ 为根的连通块 , 随便找一个和它相邻的合并一下即可 .

PS : 为什么会 MLE ? 是不是不默认开 O2 ?

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e4+10;
int n,b,res,id[MAXN],fa[MAXN],cap[MAXN],dep[MAXN],cnt[MAXN]; vector<int> G[MAXN],tmp[MAXN]; 
void calc(vector<int> vc,int op) {
	//op=0 从中间随便找一个当省会 op=1 找父亲当省会 
	if(!op) {
		++res; int capital=vc[0];
		for(auto v:vc) id[v]=res;
		cap[res]=capital;
	}
	else {
		int capital=-1; ++res;
		for(auto v:vc) if(capital==-1||dep[fa[v]]<dep[capital]) capital=fa[v];
		for(auto v:vc) id[v]=res; cap[res]=capital;
	}
	return ;
}
void solve(int u,int f) {
	dep[u]=dep[f]+1,fa[u]=f;
	tmp[u].push_back(u);
	for(auto v:G[u]) if(v!=f) solve(v,u);
	vector<int> st;
	for(auto v:G[u]) if(v!=f) {
		for(auto w:tmp[v]) st.push_back(w);
		tmp[v].clear();
		if(st.size()>=b) calc(st,1),st.clear();
	}
	for(auto v:st) tmp[u].push_back(v);
	if(tmp[u].size()>=b) calc(tmp[u],0),tmp[u].clear();
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>b;
	ffor(i,1,n-1) {
		int u,v; cin>>u>>v;
		G[u].push_back(v),G[v].push_back(u);	
	}
	solve(1,0); for(auto v:tmp[1]) cnt[v]=1;
	ffor(i,1,n) if(id[i]) {
		int flg=cnt[fa[i]];
		if(flg) {for(auto v:tmp[1]) id[v]=id[i]; tmp[1].clear(); break;}
	}
	cout<<res<<'\n';
	ffor(i,1,n) cout<<id[i]<<' '; cout<<'\n';
	ffor(i,1,res) cout<<cap[i]<<' ';
	return 0;
}