Codeforces Round 190 (Div. 1) C. Ciel the Commander（树的重心）

题目链接

https://codeforces.com/contest/321/problem/C

思路

因为我们最多只能使用$26$个等级，所以我们考虑尽可能节省地使用他们。

假设我们规定一个节点的等级为$A$，则删掉这个节点和与这个节点相连的所有边后形成的所有子树，其节点的等级必须小于$A$。

因此，我们要让分解出来的子树要尽可能的小，也就是求树的重心。

$lo{g}_{2}10^5<17<26$，所以本题一定有解。

代码

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long doubletypedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;const int N = 1e5 + 5, M = 5e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;std::mt19937 rnd(time(0));int n, root, cnt;
bool st[N];
int siz[N], mx[N];
char ans[N];
vector<int>mp[N];
void getroot(int u, int fu)
{siz[u] = 1;mx[u] = 0;for (int j : mp[u]){if (j == fu || st[j]) continue;getroot(j, u);siz[u] += siz[j];mx[u] = max(mx[u], siz[j]);}mx[u] = max(mx[u], cnt - siz[u]);if (mx[root] > mx[u]) root = u;
}
void dfs(int u, int res)
{st[u] = true;ans[u] = 'A' + res;int num = cnt;for (int j : mp[u]){if (st[j]) continue;if (siz[j] > siz[u])cnt = num - siz[u];else cnt = siz[j];root = 0;mx[root] = n;getroot(j, u);dfs(root, res + 1);}
}
void solve()
{cin >> n;for (int i = 1, a, b; i < n; i++){cin >> a >> b;mp[a].push_back(b);mp[b].push_back(a);}mx[root] = cnt = n;getroot(1, -1);dfs(root, 0);for (int i = 1; i <= n; i++){cout << ans[i] << " ";}cout << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}