[CF321C] Ciel the Commander - 点分治
Description
给定一棵树,给每个点分配一个等级用英文字母表示,满足任意两个等级相同的点 x,y 的路径上必然有一个等级更高的点 z。
Solution
考虑选择点 p 并分配给它最大的权重,此时若删除点 p,留下的若干棵子树 t1,t2,...,tm 他们之间的问题已经解决了,只需要解决他们之内的问题。
这构成了一个天然的分治结构,我们希望使得分治结构的树高最小,采用点分治的策略,每次选择重心作为分治点即可。
回忆一下我们是怎样实现点分治的。每个点设置一个访问标记,代表这个点是否已经被作为分治点处理过,那么我们当前要处理的就是由未标记点构成的一个连通块。我们首先计算出每个点的子树大小以及最大子树大小(通过一次 DFS + 一次遍历实现),并找到具有最小的最大子树大小的点,标记这个点,给它分配级别,然后处理其所有未标记过的邻居所引导的连通块。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
vector<int> g[N];
int n, m, t1, t2, t3, t4, vis[N], siz[N], maxsiz[N], flag = 1;
char ans[N];
vector<int> current_block;
// 计算子树大小和最大子树大小
void calc(int p, int fa)
{
siz[p] = 1;
current_block.push_back(p);
maxsiz[p] = 0;
for (auto q : g[p])
{
if (q != fa && !vis[q])
{
calc(q, p);
siz[p] += siz[q];
maxsiz[p] = max(maxsiz[p], siz[q]);
}
}
}
// 分治核心
void solve(int p, int depth)
{
// 判断是否被访问过
if (vis[p])
return;
// 找出最大子树大小最小的点
current_block.clear();
calc(p, 0);
int root = 0;
maxsiz[0] = 1e18;
for (auto i : current_block)
{
maxsiz[i] = max(1ull * maxsiz[i], 1ull * current_block.size() - siz[i]);
if (maxsiz[i] < maxsiz[root])
root = i;
}
// 分配
p = root; // !
vis[p] = 1;
ans[p] = 'A' + depth;
if (depth >= 26)
flag = 0;
// 递归下去
for (auto q : g[p])
{
solve(q, depth + 1);
}
}
// 主程序
signed main()
{
// freopen("D:\\XCPCWorkspace\\cf\\contest\\321\\c\\in1.txt", "r", stdin);
// 读入数据
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i < n; i++)
{
cin >> t1 >> t2;
g[t1].push_back(t2);
g[t2].push_back(t1);
}
// 处理
solve(1, 0);
// 输出
if (flag)
{
for (int i = 1; i <= n; i++)
cout << ans[i] << " ";
cout << endl;
}
else
{
cout << "Impossible!" << endl;
}
}