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

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;
}