Codeforces Round 592 (Div. 2) D. Paint the Tree

Link: D. Paint the Tree

D. Paint the Tree

Description:
You are given a tree consisting of n vertices. A tree is an undirected connected acyclic graph.

Example of a tree
You have to paint each vertex into one of three colors. For each vertex, you know the cost of painting it in every color.

You have to paint the vertices so that any path consisting of exactly three distinct vertices does not contain any vertices with equal colors. In other words, let's consider all triples (x,y,z) such that x≠y,y≠z,x≠z, x is connected by an edge with y, and y is connected by an edge with z. The colours of x, y and z should be pairwise distinct. Let's call a painting which meets this condition good.

You have to calculate the minimum cost of a good painting and find one of the optimal paintings. If there is no good painting, report about it.

Input
The first line contains one integer n (3≤n≤100000) — the number of vertices.

The second line contains a sequence of integers c1,1,c1,2,…,c1,n (1≤c1,i≤1e9), where c1,i is the cost of painting the i-th vertex into the first color.

The third line contains a sequence of integers c2,1,c2,2,…,c2,n (1≤c2,i≤1e9), where c2,i is the cost of painting the i-th vertex into the second color.

The fourth line contains a sequence of integers c3,1,c3,2,…,c3,n (1≤c3,i≤1e9), where c3,i is the cost of painting the i-th vertex into the third color.

Then (n−1) lines follow, each containing two integers uj and vj (1≤uj,vj≤n,uj≠vj) — the numbers of vertices connected by the j-th undirected edge. It is guaranteed that these edges denote a tree.

Output
If there is no good painting, print −1.

Otherwise, print the minimum cost of a good painting in the first line. In the second line print n integers b1,b2,…,bn (1≤bi≤3), where the i-th integer should denote the color of the i-th vertex. If there are multiple good paintings with minimum cost, print any of them.

Examples
input
3
3 2 3
4 3 2
3 1 3
1 2
2 3
output
6
1 3 2
input
5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 3
output
-1
input
5
3 4 2 1 2
4 2 1 5 4
5 3 2 1 1
1 2
3 2
4 3
5 4
output
9
1 3 2 1 3
Note
All vertices should be painted in different colors in the first example. The optimal way to do it is to paint the first vertex into color 1, the second vertex — into color 3, and the third vertex — into color 2. The cost of this painting is 3+2+1=6.

Problem solving:
这道题的意思就是给你一个树和三种颜色，每个点染这三种颜色都会有不同的消费，并且让任意三个可以连起来的顶点都不能有同一种颜色，问你在最优策略下，怎样染色花费最少。如果不能满足任意三个可以连起来的顶点不会出现同一种颜色，输出-1，如果有满足条件的，首先输出最小花费，然后输出每个顶点的染色情况。

一开始还以为是多复杂的图论题，后来发现只是个思维题。。。首先我们要知道

1. 如果这个树不是一条链状的，就一定不能满足任意三个可以连起来的顶点不会出现同一种颜色的条件
2. 如果前三个顶点的颜色确定了，那么后面所有的顶点的颜色就都确定了。也就是说假设前三个顶点的颜色为ABC，那么这颗链状树的染色情况就是ABCABCABCABCABC......，所以只要我们知道了前三个点的颜色，后面的顶点直接对三取余就可以知道它的颜色了。

证明我们先放在后面。现在你已经知道这两个条件了。那么是不是就很简单了，直接暴力就行。首先判断一下这个树是不是一条链，如果不是直接输出'-1'，如果是就先用dfs算出每个顶点的层数，然后枚举前三个点的情况，这总共才六种情况，暴力枚举即可，算出最小值，更新最小值的时候顺便更新一下每个点的颜色。这里因为颜色都是确定的，所以我们只看第i个顶点的层数对3的余数即可知道它的颜色。

证明：

1. 如果一条树是非链性的，比如说这样的一棵树 1和2相邻，颜色不能相同，这已经用了两种了。因为123和124都是联通的，所以可以知道3和4都是第三种颜色。但是这样的话，234中就有了颜色相同的点，所以必须是链状的才能满足题目中的要求。
2. 假设一个链状树ABCDEFG，ABC的颜色确定为123的话，那么D的颜色一定是1，因为BCD中不能出现颜色相同的。即证2。

所以这道题就很简单了，判断后暴力枚举。具体实现的时候会有一些细节需要注意，具体看代码注释
Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb    push_back
const int   maxn = 1e5 + 10;
int         n, c[maxn][3], Ans[maxn], C[5] = { 0, 1, 2, 3 }, dep[maxn], in[maxn];
ll          s[3][3];
vector<int> V[maxn];
void dfs(int u, int f)
{
    for (int i = 0; i < V[u].size(); i++)
    {
        if (V[u][i] != f)
        {
            dep[V[u][i]] = dep[u] + 1;
            dfs(V[u][i], u);
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> c[j][i];
        }
    }
    for (int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        V[v].pb(u); V[u].pb(v);
        in[u]++, in[v]++;
        if (in[u] > 2 || in[v] > 2) //这里用来判断是不是链状的
        {
            puts("-1");
            return 0;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 1) //找到根节点然后开始dfs，算出每个点的层数
        {
            dfs(i, 0);
            break;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++)
            s[dep[i] % 3][j] += c[i][j];//初始化处理对3取模分别为0，1，2的顶点们染成三种颜色之一的颜色的花费，方便下面暴力枚举的时候使用
    ll ans = 0x3f3f3f3f3f3f3f3f;
    do
    {
        ll mid = 0;
        for (int i = 1; i <= 3; i++)
            mid += s[i - 1][C[i] - 1];
        if (mid < ans)
        {
            ans = mid;
            for (int i = 1; i <= 3; i++)
                Ans[i] = C[i];
        }
    } while (next_permutation(C + 1, C + 4));//暴力枚举，三种颜色，三个顶点的情况
    cout << ans << endl;
    for (int i = 1; i <= n; i++)
        cout << Ans[dep[i] % 3 + 1] << " ";
    return 0;
}

代码里面有很多对下标的处理，一定要注意。