Codeforces 1244D《Paint the Tree》

因为细节问题没过 pretest 导致我掉分的题目

题意翻译

有一棵树,有3种颜色,第i个节点染成第j种颜色的代价是$c_{j,i}$,现在要你求出一种染色方案,使得总代价最小,且对于任意三个相邻的节点,颜色不能相同。输出最小代价与其中一种方案。无解输出$-1$。

$3\le n\le 10^5$

输入输出样例

输入 #1

1
2
3
4
5
6
3
3 2 3
4 3 2
3 1 3
1 2
2 3

输出 #1

1
2
6
1 3 2

输入 #2

1
2
3
4
5
6
7
8
5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 3

输出 #2

1
-1

输入 #3

1
2
3
4
5
6
7
8
5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 4

输出 #3

1
2
9
1 3 2 1 3

解析

拿到样例之后就随便手玩一下,然后再随便举几个例子
发现这样一个奇怪的事情:

好像任意的$k(k \geq 2)$叉树都没法染色。。。

这里直接用二叉树的情况解释一下

1
2
3
4
5
graph LR;
A --> B
A --> C
B --> D
B --> E

发现在无论怎么染色,对 A、B、D、E 进行染色总会冲突

所以分析了半天可以发现这样一个有趣的性质:

一棵树能被正确进行染色当且仅当这棵树为一条链。


判完 -1 再来想一想怎么搞一条链的情况

不会了啊。。。完了今晚要掉分了

想一下暴力是怎么做的:$3^n$枚举所有的点怎么填颜色,然后扫一遍判断。继续手玩一条链的情况,发现一个事情:

两个点确定了,整条链的染色方案就唯一确定了。


做法就出来了。

首先判断树是否为一条链(判断每个点的度),不为链则 Failed;
然后两重循环大力枚举前两个点的颜色,之后扫一遍确定其他点的颜色,顺便算出花费,更新答案
输出最终答案


实现的时候要注意细节很多。。。我比赛的时候因为时间不太够写的很急,结果没过 pretest。。。

代码实现

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
87
88
89
90
91
92
93
94
95
//
// Created by HandwerSTD on 2019/10/27.
// Copyright (c) 2019 HandwerSTD. All rights reserved.
// Title: Paint the Tree
//
// sto Qingyu orz
// 感谢真神sqy无私的教诲。膜时队者处处阿克,只因大师sqy在他背后。不膜大师者违背了真神的旨意,真神必将降下天谴,
// 使其天天爆零
// 我不由自主地膜拜真神sqy。
//

#include <iostream>
#include <cstdio>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 100000 + 10;

int n, linkTop;
long long int ans = 10000000000000000;
long long int cost[MAXN][4];
int degree[MAXN];
std::vector<int> head[MAXN];
int next[MAXN];
long long int col[MAXN], fcol[MAXN];

void DFS(int now, int pre) {
for (auto v : head[now]) {
if (v == pre) continue;
next[now] = v;
DFS(v, now);
}
}
void Search(int now, int pre, int ppre) {
for (; now; now = next[now]) {
if (col[ppre] == 1) {
if (col[pre] == 2) col[now] = 3;
else col[now] = 2;
} else if (col[ppre] == 2) {
if (col[pre] == 1) col[now] = 3;
else col[now] = 1;
} else {
if (col[pre] == 1) col[now] = 2;
else col[now] = 1;
}
ppre = pre; pre = now;
}
long long int fcost = 0;
for (int i = 1; i <= n; ++i) {
fcost += cost[i][col[i]];
}
if (ans >= fcost) {
ans = fcost;
for (int i = 1; i <= n; ++i) {
fcol[i] = col[i];
}
}
}

int main() {
cin >> n;
for (int c = 1; c <= 3; ++c) {
for (int i = 1; i <= n; ++i) {
cin >> cost[i][c];
}
}
for (int i = 1; i <= n - 1; ++i) {
int u = 0, v = 0;
scanf("%d %d", &u, &v);
head[u].push_back(v); ++degree[u];
head[v].push_back(u); ++degree[v];
}
for (int i = 1; i <= n; ++i) {
if (degree[i] > 2) return (0 & puts("-1"));
if (degree[i] == 1 && !linkTop) linkTop = i;
}
DFS(linkTop, 0);
for (int i = 1; i <= 3; ++i) {
col[linkTop] = i;
int linkNext = next[linkTop];
for (int j = 1; j <= 3; ++j) {
col[linkNext] = j;
if (i == j) continue;
Search(next[linkNext], linkNext, linkTop);
}
}
cout << ans << endl;
for (int i = 1; i <= n; ++i) {
cout << fcol[i] << (i == n ? '\n' : ' ');
}
return 0;
}