题意：
用 'A'~'Z' 给一棵树上的点染色，要求若两点字符相同则两点间的路径上一定有字符更小的点。
思路：
法一：点分治
树的重心能把树划分成每块大小不超过 \(n/2\) 的连通块
首先给整棵树的重心赋字符 A（显然整棵树中不能有两个 A），然后用 B~Z 处理去掉重心后的每个连通块。
\(log(1e5)<26\) 所以是够用的
const signed N = 5 + 1e5;
int n; vector<int> G[N];
bool vis[N]; int sz[N], res, root, tot;
void getCentroid(int u, int fa) {
sz[u] = 1; int mx = 0;
for(int v : G[u]) if(v != fa && !vis[v]) {
getCentroid(v, u);
sz[u] += sz[v], mx = max(mx, sz[v]);
}
mx = max(mx, tot-sz[u]);
if(mx < res) res = mx, root = u;
}
char ans[N];
void dfs(int u, int fa) {
res = INF, tot = tot ? sz[u] : n; //init
getCentroid(u, fa), u = root, vis[u] = 1;
ans[u] = fa ? ans[fa]+1 : 'A';
for(int v : G[u]) if(v != fa && !vis[v])
dfs(v, u);
}
void sol() {
cin >> n; for(int i = 1; i < n; i++) {
int x, y; cin >> x >> y;
G[x].pb(y), G[y].pb(x);
}
dfs(1, 0);
for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
法二：从下往上模拟
对某点 \(u\)，假设 \(u\) 的后代已经处理完毕，我们希望给 \(u\) 安排一个尽量大的字符
定义一个 \(u\) 的后代 \(v\) “暴露” 当且仅当从 \(v\) 到 \(u\) 的路径上没有比 \(v\) 小的点，那么 \(u\) 只需满足两个条件：
- \(u\) 不能与任何一个暴露点相等
- 若某字符 \(ch\) 对 \(u\) 的两个不同儿子来说都是暴露的，则 \(u\) 的字符须小于 \(ch\)
字符集很小，暴力检查即可。
树根随便取（比如取点1为根），一定有答案。不会证明...
const signed N = 5 + 1e5;
int n; vector<int> G[N];
int ans[N];
int dfs(int u, int fa) { //返回子树中暴露的字符集
int Su = 0;
vector<int> cnt(26);
for(int v : G[u]) if(v != fa) {
int Sv = dfs(v, u); Su |= Sv;
for(int i = 0; i <= 25; i++)
if(Sv>>i&1) cnt[i]++;
}
//处理在不同儿子子树中出现至少两次的字符
ans[u] = 25; for(int i = 25; i; i--)
if(cnt[i] >= 2) ans[u] = i - 1;
//ans[u]不能等于任意暴露字符
while(Su>>ans[u]&1) ans[u]--;
return Su & ((1<<ans[u])-1) | (1<<ans[u]); //大于ans[u]的字符都不暴露
}
void sol() {
cin >> n; for(int i = 1; i < n; i++) {
int x, y; cin >> x >> y;
G[x].pb(y), G[y].pb(x);
}
dfs(1, 0);
for(int i = 1; i <= n; i++) cout << char(ans[i] + 'A') << ' ';
}