题目链接：http://codeforces.com/contest/1244/problem/D
题目大意：给你一棵树，让你染色，一共有3种颜色.i节点涂成颜色1代价为a[i], 2:b[i], 3:c[i]。

并且树一条路径上连续的三个节点不能有颜色重复。

输出最小代价，或者不能做到-1。

思路：如果不是一条链就无法做到。很好证明。

如果是一条链。f[i][a][b]:i节点染色颜色a，它的儿子染颜***的最小代价。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
 
int s[100005][3];
int d[100005]={0};
LL f[100005][3][3]={0};
int vis[100005];
vector<int> v[100005], st;
int E=0;
void dfs(int u, int fa){
 
    st.push_back(u);
    if(v[u].size()==1&&fa!=-1){
        E=u;
        f[u][0][0]=f[u][0][1]=f[u][0][2]=s[u][0];
        f[u][1][0]=f[u][1][1]=f[u][1][2]=s[u][1];
        f[u][2][0]=f[u][2][1]=f[u][2][2]=s[u][2];
        return;
    }
    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to==fa){
            continue;
        }
        else{
            dfs(to, u);
            for(int k1=0; k1<=2; k1++){
                f[u][k1][0]=f[u][k1][1]=f[u][k1][2]=1ll<<60;
                for(int k2=0; k2<=2; k2++){
                    for(int k3=0; k3<=2; k3++){
                        if(k1!=k2&&k1!=k3&&k2!=k3){
                            f[u][k1][k2]=min(f[to][k2][k3]+s[u][k1], f[u][k1][k2]);
                        }
                    }
                }
            }
        }
    }
}
 
int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<3; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &s[j][i]);
        }
    }
    int maxd=0, root=0;
    for(int i=1; i<n; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
        d[a]++, d[b]++;
        maxd=max(d[a], maxd);
        maxd=max(d[b], maxd);
    }
    for(int i=1; i<=n; i++){
        if(d[i]==1){
            root=i;
            break;
        }
    }
    //cout<<root<<endl;
    if(maxd>2){
        printf("-1\n");
        return 0;
    }
    dfs(root, -1);
    LL m=1ll<<60;
    int x, y;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(i!=j&&f[root][i][j]<m){
                m=f[root][i][j];
                x=i, y=j;
            }
        }
    }
    printf("%lld\n", m);
    for(int i=0; i<n; i++){
        vis[st[i]]=x;
        int z=3-x-y;
        x=y, y=z;
    }
    for(int i=1; i<=n; i++){
        printf("%d ", vis[i]+1);
    }
 
    return 0;
}