You are given a tree consisting of nn 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)(x,y,z) such that x≠y,y≠z,x≠zx≠y,y≠z,x≠z, xx is connected by an edge with yy, and yy is connected by an edge with zz. The colours of xx, yy and zz 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 nn (3≤n≤100000)(3≤n≤100000) — the number of vertices.
The second line contains a sequence of integers c1,1,c1,2,…,c1,nc1,1,c1,2,…,c1,n (1≤c1,i≤109)(1≤c1,i≤109), where c1,ic1,i is the cost of painting the ii-th vertex into the first color.
The third line contains a sequence of integers c2,1,c2,2,…,c2,nc2,1,c2,2,…,c2,n (1≤c2,i≤109)(1≤c2,i≤109), where c2,ic2,i is the cost of painting the ii-th vertex into the second color.
The fourth line contains a sequence of integers c3,1,c3,2,…,c3,nc3,1,c3,2,…,c3,n (1≤c3,i≤109)(1≤c3,i≤109), where c3,ic3,i is the cost of painting the ii-th vertex into the third color.
Then (n−1)(n−1) lines follow, each containing two integers ujuj and vjvj (1≤uj,vj≤n,uj≠vj)(1≤uj,vj≤n,uj≠vj) — the numbers of vertices connected by the jj-th undirected edge. It is guaranteed that these edges denote a tree.
Output
If there is no good painting, print −1−1.
Otherwise, print the minimum cost of a good painting in the first line. In the second line print nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤3)(1≤bi≤3), where the ii-th integer should denote the color of the ii-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 3Output
6 1 3 2Input
5 3 4 2 1 2 4 2 1 5 4 5 3 2 1 1 1 2 3 2 4 3 5 3Output
-1Input
5 3 4 2 1 2 4 2 1 5 4 5 3 2 1 1 1 2 3 2 4 3 5 4Output
9 1 3 2 1 3Note
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 11, the second vertex — into color 33, and the third vertex — into color 22. The cost of this painting is 3+2+1=63+2+1=6.
题意： 给你一棵树， 一共有三种颜色，给树的节点进行上色， 每相邻的三个 节点的颜色不能 相同，每种颜色都有n 种价位。
求既满足要求，总费用又最小的方式，并打印出最小总费用是多少。
题解：一共三种颜色，每相邻的三个节点的颜色又不能一样。即一个 节点，当其度大于2的时候，就不能满足结果。所以 针对于 这道题我们可以把一棵树改变成一条链。从度为一的开始 进行涂色，当前两种颜色确定后，后面的颜色也 唯一了。
难点：记录路径！！！
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<vector> using namespace std; vector<int>g[100010]; vector<int>s;//记录路径 int c[3][100010]; int book[100010]; //int col[6][3]= {1,2,3,1,3,2,2,3,1,2,1,3,3,2,1,3,1,2}; int col[6][3]= {1,2,0,1,0,2,2,0,1,2,1,0,0,2,1,0,1,2}; int C[100010]; void dfs(int x) { book[x]=1; s.push_back(x);//记录路径 int l=g[x].size(); //printf("%d %d********>\n",x,l); for(int i=0; i<l; i++) { int v=g[x][i]; // printf("%d %d %d---->\n",x,i,v); if(book[v]==0) dfs(v); } } int main() { int n; while(~scanf("%d",&n)) { for(int i=0; i<3; i++) { for(int j=1; j<=n; j++) { scanf("%d",&c[i][j]); } } int a,b; memset(book,0,sizeof(book)); for(int i=1; i<n; i++) { scanf("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } for(int i=1; i<=n; i++) { if(g[i].size()>2) { printf("-1\n"); return 0; } } for(int i=1; i<=n; i++) { if(g[i].size()==1) { dfs(i); break; } } long long sum,minn=99999999999999999; long long id; for(int i=0;i<6;i++) { sum=0; for(int j=0;j<s.size();j++) { sum+=c[col[i][j%3]][s[j]];//-0-0 } if(sum<minn) { minn=sum; id=i; } } printf("%lld\n",minn); for(int i=0;i<n;i++)//s[i]代表路径中的顶点数 { C[s[i]]=col[id][i%3]+1;//C[]表示该顶点涂的哪一个颜色 } for(int i=1;i<=n;i++) { if(i==1) printf("%d",C[i]); else printf(" %d",C[i]); } printf("\n"); } return 0; }
