H - Royal Federation
\(\mathsf{\color{Thistle}Statement}\)
给定一棵 \(n\) 个点的树，将其划分为 \(m\) 个集合（\(m\) 可以为任意正整数），对于每个集合，顷定其特殊点，使得该点可以到达属于该集合内的所有点只经过集合内的点（注意特殊点可以不在集合内），其中集合大小要求在 \(B\sim 3B\) 之间。
\(\mathsf{\color{Thistle}Solution}\)
通过 DFS 由底向上合并，对于点 \(u\)，考虑 \(u\) 的所 \(u\) 的儿子 \(v_i\)，对于 \(\forall i,j\) 使得 \(v_i< B,v_j<B\)，合并 \(i,j\)。若合并后还是 \(<B\)，则在与其余儿子合并。
如果按照上述合并方式，最终剩余 \(1\) 个儿子 \(<B\)，但无法合并，则将该儿子与 \(u\) 合并（目的是当统计 \(u\) 的父亲的时候，使得该儿子所在集合可以进一步合并）
注意：当处理完整棵树之后，有可能 \(1\) 点所在的集合 \(<B\)，如若真如此，则将 \(1\) 点所在集合与下面的相邻的集合合并即可，可以证明合并完之后仍在 \(B\sim 3B\) 之间。
Proof
注意到与 1 点相邻的集合是由两个小于 B 的集合合并而成，故必然 < 2B。而当前 1 点所在的集合大小 < B，所以合并后 < 3B。
合并使用并查集即可，特殊点（原题为省会）的维护也是简单的（具体见代码吧）。时间复杂度 \(O(n\alpha(n))\)。
\(\mathsf{\color{Thistle}Code}\)
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e4 + 10;
int n, m, B;
int par[N], sz[N], ctr[N], id[N];
std::vector<int> g[N];
int find(int x) {
if (par[x] != x) par[x] = find(par[x]);
return par[x];
}
void dfs1(int u, int fa) {
vector<PII> tmp;
for (auto v : g[u]) {
if (v == fa) continue;
dfs1(v, u);
if (sz[find(v)] < B) tmp.push_back({sz[find(v)], v});
}
while (tmp.size() > 1) {
auto a = tmp.back(), b = tmp[tmp.size() - 2];
tmp.pop_back(), tmp.pop_back();
int pa = find(a.se), pb = find(b.se);
par[pa] = pb, sz[pb] += sz[pa];
if (sz[pb] < B) tmp.push_back({sz[pb], b.se});
else ctr[pb] = u;
}
if (tmp.size()) {
int pa = find(u), pb = find(tmp[0].se);
par[pa] = pb, sz[pb] += sz[pa];
if (sz[pb] >= B) ctr[pb] = u;
}
}
bool ok = 0;
void dfs2(int u, int fa) {
if (ok) return;
for (auto v : g[u]) {
if (v == fa) continue;
if (find(v) != find(u)) {
par[find(v)] = find(u), ok = 1;
return;
}
else dfs2(v, u);
if (ok) return;
}
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
freopen("royal.in", "r", stdin);
freopen("royal.out", "w", stdout);
cin >> n >> B;
for (int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
}
for (int i = 1; i <= n; i ++ ) par[i] = i, sz[i] = 1;
if (n <= 3 * B) {
cout << 1 << endl;
for (int i = 1; i <= n; i ++) cout << 1 << " ";
cout << 1 << endl;
return 0;
}
dfs1(1, -1);
if (sz[find(1)] < B) dfs2(1, -1);
for (int i = 1; i <= n; i ++)
if (find(i) == i)
id[find(i)] = ++ m;
cout << m << endl;
for (int i = 1; i <= n; i ++)
cout << id[find(i)] << " ";
cout << endl;
for (int i = 1; i <= n; i ++)
if (find(i) == i) {
if (!ctr[i]) cout << i << " ";
else cout << ctr[i] << " ";
}
return 0;
}