[CF321C] Ciel the Commander

[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;
    }
}