Codeforces Round #411 (Div. 2)

E. Ice cream coloring

题意

  • 结点为n的树
  • 有m种类型的冰淇淋
  • 每个结点上都有si种冰淇淋,这si种冰淇淋两两相邻(即形成完全图)
  • 任意两个结点若有相同类型的冰淇淋,则这两个结点在树上必定相邻(即存在边)

问题

  • 对m种类型的冰淇淋构成的图进行染色,相邻的冰淇淋不能同色,问至少需要多少种颜色,并给出方案

思路

  • 由于拥有同种冰淇淋的结点相邻,且这是一个树,无环。
  • 故假设树上有三个节点a,b,c.(a,b),(b,c)∈E,
  • 那么满足S(a)∩S(C)∈S(b),[S(a) - S(a)∩S(C)]∩[S(c) - S(a)∩S(C)]=空集,即a和c剩下的冰淇淋之间不相邻, 那么若b结点的冰淇淋全部染色了,则a剩下的冰淇淋染色与c剩下的冰淇淋染色是独立的,容易得到所需要的颜色数 ans = max( si )
  • S(x)即节点x拥有的冰淇淋,E表示树的边
  • 对于每个结点的冰淇淋构成的子图,标记下已经被染色的冰淇淋种类,剩下未被染色的冰淇淋选择在本完全中未被使用的颜色即可

代码

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
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define repp(i,a,b) for(int i=b; i>=a; --i)
#define mp make_pair
#define pb push_back
#define ms(a, b) memset(a, b, sizeof(a))
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int>vi;
typedef map<int, int> mi;
const int maxn = 1e6+7;

int ans=0;
vi s[maxn];
vi e[maxn];
int c[maxn];
mi q;

void dfs(int now, int pre){

q.clear();

int len = s[now].size() - 1;

// 枚举该结点下每种冰淇淋,记录在之前已经被涂过的冰淇淋
rep(i, 0, len){
if(c[ s[now][i] ]){
q[ c[s[now][i]] ] = 1;
}
}

int t = 0;

rep(i, 0, len){
int inx = s[now][i];
if(c[inx]) continue; // 已经涂色的跳过
while(q[++t]){} // 选择一个未被涂过的颜色
c[inx] = t; // 涂色
}

len = e[now].size()-1;

rep(i, 0, len){
if(e[now][i] != pre){ // 树,无环,往下搜便可
dfs(e[now][i], now);
}
}

return ;
}

int main(){
int n, m, p, x;
while(~scanf("%d %d", &n, &m)){
ans=0;
if(m) ans = 1; //注意:如果m不为0, 那么至少需要一种颜色
ms(c, 0); // 颜色清空
rep(i, 1, n){
scanf("%d", &p);
ans = max(ans, p);// p个节点的完全图需要p种颜色
rep(j, 0, p-1) {
scanf("%d", &x); //
s[i].pb(x);
}
}

// 建树,连边
rep(i, 1, n-1){
int u, v;
scanf("%d%d", &u, &v);
e[u].pb(v);
e[v].pb(u);
}

dfs(1, -1); // 从第一个结点开始涂色

printf("%d\n", ans);
rep(i, 1, m){
printf("%d ", c[i]?c[i]:1);
}
printf("\n");
}
return 0;
}