Paint the Tree

发表于 分类于 ，

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

    $3\le n\le 10^5$

Paint the Tree

Created by LXC on Thu Apr 25 16:17:00 2024

https://codeforces.com/problemset/problem/1244/D

ranting: 1800

tag: brute force, constructive algorithms, dp, graphs, implementation, trees

problem

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

$3\le n\le 10^5$

solution

这棵树是一条链。否则不符合要求。

当确定两种颜色时，第三种颜色也就确定了。然后可以三种颜色的排列，维护答案最小值

code

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

const ll inf = 0x3f3f3f3f3f3f3f3f;

void sol() {
    int n;
    cin >> n;
    vector w(3, vector<int>(n));
    for (auto& i:w) {
        for (auto& j:i) {
            cin >> j;
        }
    }
    vector<vector<int>> g(n);
    for (int i=1; i<n; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int d1 = 0, d2 = 0;
    vector<int> pt;
    for (int i=0; i<n; i++) {
        if (g[i].size() == 1) d1++, pt.push_back(i);
        if (g[i].size() == 2) d2++;
    }
    if (d1 == 2 && d2 == n-2) {
        vector<int> s;
        function<void(int, int)> dfs = [&](int x, int fa) {
            s.push_back(x);
            for (int y:g[x]) {
                if (y == fa) continue;
                dfs(y, x);
            }
        };
        dfs(pt[0], -1);
        // cout << s << endl;
        ll f[n][3][3];
        memset(f, 0x3f, sizeof(f));
        int lk[n][3][3];
        memset(lk, -1, sizeof(lk));
        for (int i=0; i<n; i++) {
            for (int a=0; a<3; a++) {
                for (int b=0; b<3; b++) {
                    for (int c=0; c<3; c++) {
                        if (a == b || b == c || a == c) continue;
                        if (i>=1) {
                            if (f[i][b][c] > f[i-1][a][b] + w[c][s[i]]) {
                                f[i][b][c] = f[i-1][a][b] + w[c][s[i]];
                                lk[i][b][c] = a;
                            }
                        }
                        else 
                            f[i][b][c] = w[c][s[i]];
                        // cout << i << " " << b << " " << c << " : " << f[i][b][c] << endl;
                    }
                }
            }
        }
        int a = 0, b = 1;
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                if (i == j) continue;
                if (f[n-1][i][j] < f[n-1][a][b]) {
                    a = i;
                    b = j;
                }
            }
        }
        cout << f[n-1][a][b] << "\n";
        vector<int> ans(n);
        for (int i=n-1; i>=0; i--) {
            ans[s[i]] = b;
            int t = lk[i][a][b];
            b = a;
            a = t;
        }
        // cout << ans << endl;
        for (int i:ans) {
            cout << i + 1 << " ";
        }
        cout << "\n";
    } else {
        cout << "-1\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

const ll inf = 0x3f3f3f3f3f3f3f3f;

void sol() {
    int n;
    cin >> n;
    vector w(3, vector<int>(n));
    for (auto& i:w) {
        for (auto& j:i) {
            cin >> j;
        }
    }
    vector<vector<int>> g(n);
    for (int i=1; i<n; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int d1 = 0, d2 = 0;
    vector<int> pt;
    for (int i=0; i<n; i++) {
        if (g[i].size() == 1) d1++, pt.push_back(i);
        if (g[i].size() == 2) d2++;
    }
    if (d1 == 2 && d2 == n-2) {
        vector<int> s;
        function<void(int, int)> dfs = [&](int x, int fa) {
            s.push_back(x);
            for (int y:g[x]) {
                if (y == fa) continue;
                dfs(y, x);
            }
        };
        dfs(pt[0], -1);
        // cout << s << endl;
        auto check = [&](vector<int> a) {
            ll cnt = 0;
            for (int i=0; i<n; i++) {
                cnt += w[a[i%3]][s[i]];
            }
            return cnt;
        };
        vector<int> v = {0,1,2};
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                for (int k=0; k<3; k++) {
                    if (i == j || j == k || i == k) continue;
                    vector<int> vt = {i,j,k};
                    if (check(vt) < check(v)) {
                        v = vt;
                    }
                }
            }
        }
        cout << check(v) << "\n";
        vector<int> ans(n);
        for (int i=0; i<n; i++) {
            ans[s[i]] = v[i%3];
        }
        // cout << ans << endl;
        for (int i:ans) {
            cout << i + 1 << " ";
        }
        cout << "\n";
    } else {
        cout << "-1\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}