codeforces Ciel the Commander

本文从WordPress迁移而来, 查看全部WordPress迁移文章

数据结构 树的重心

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

题意:给出一棵无根树,给出A-Z,26个字母,分别代表权值,A权值最高,Z权值最低。树中如果有两个点的权值相同,那么在这两点的路径上,一定要有至少1个点的权值高于他们。满足这个要求构造出一棵合法的树

近期内做的最有意思的一题,想了很久问了很多人,结合了各种不同的思路做出来了,最重要的是学会了树中重心这个概念

这题树的节点数达到10^5,但是可用的字母只有26个,这看起来是个很困难的问题(确实也挺困难的),但是搞懂之后才知道,其实26个字母给多了,根本用不完。所以这题,他说无解的话输出impossible,但是这题是一定有解的,因为26个字母一定够用

树的重心:选出一个点,让其作为树的根,它有k个儿子,那么使到每个儿子子树的节点总数不超过总点数的一半,那么这个点就是树的重心

一个不断寻找重心的过程

第1次(层)寻找的重心染色A

第2次(层)寻找的重心染色B

依次类推

每次寻找到一个重心,就将它去掉,整个树被断裂为几个子树,再在每个子树里做同样的工作—找重心

直到所有点都被染色

可以证明 2^26 > 10^5 , 这个问题一定有解,证明类似于二分那样

因为重心是以子孙总数不超过整个树的一半来定义的,所以每找到一个重心并去除掉后

剩下的子树中,每棵子树的总数都不会超过原来的一半,只要分割log n 次,剩下的子树个数就是1了

而染色可以说是按照层次关系来染色的,每层用一种色,所以只用了log n 种色

A只能有1个点能填,它是整个树的重心,去掉A这个点,出现了k个子树

这k个子树分别找出各自的重心,这k个重心填B,所以B填了k次…………..

思考过程

  1. 试着想想,如果是一条10^5的长链要怎么填
  2. 一度在考虑,如果定了1为根,同一深度的节点要怎么填,这种思考方法是错误的
  3. 一度想到,在整个树中找到重心,填上A,然后以从外围向内包围的方式去填字母;虽然很相似,但还是错的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100010
#define cl memset
#define pb push_back

int n;
vector<int>e[N];
int color[N];
int sz[N];

void dfs(int u ,int fa){ //dfs只要是为了找到一个子树下有多少子孙后代,但是每次dfs的时候方向都不同
sz[u] = 1;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v != fa && !color[v]){
dfs(v,u);
sz[u] += sz[v]; //dp出以u为根的子树下面有多少子孙后代
}
}
}

int find_center(int x){ //找到x为根的子树的重心

dfs(x,-1);

int cap = sz[x] / 2; //重心判断标准
int par = -1 , son , cen = x;

while(true){
bool ok = true;
for(int i = 0; i < e[cen].size(); i++){
son = e[cen][i];
if(!color[son] && son != par && sz[son] > cap){
ok = false;
par = cen; cen = son;
break;
//还存在一个儿子分支的总数超过了总数的一半,那么从这个儿子走一步,重新再来
}
}
if(ok) return cen; //这个cen就是重心,因为再没有儿子分支的总数超过一半
}
}

void solve(int u ,int val){ //解决掉以u为根的子树的全部染色问题,从val这个颜色开始染
int cen = find_center(u); //找到以u为根的子树的重心
color[cen] = val; //给重心染色

// printf("cen = %d color = %d\n",cen,color[cen]);

for(int i = 0; i < e[cen].size(); i++){
int v = e[cen][i];
if(!color[v])
solve(v,val+1); //以重心为中心,找到它周围所有分支的重心,然后染色
}

}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i < n ;i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}

cl(color,0,sizeof(color)); //给所有节点染色,0代表还没染,1代表A,26代表Z
solve(1,1); //定根为1,解决掉1为根的子树,从1开始染色
for(int i = 1; i <= n; i++)
printf("%c ",'A' + color[i] - 1);
printf("\n");
}
return 0;
}