Codeforces 1244D《Paint the Tree》

十月 28, 2019 3634

因为细节问题没过 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;
}