显然的，如果一个点的度大于$2$，无解。

证明：

设一个点$a$的度为$3$，连接的三个点分别为$x$，$y$，$z$

则：$a$，$x$，$y$两两异色，$a$，$y$，$z$两两异色，但是只有$3$种颜色，并不存在一种方案满足条件（若满足前者，则满足不了$z$与$a$，$x$，$y$都异色）。

所以整个树就是一条链。

然后就能线性递推了。只要枚举前两个点的颜色就行了。

时间复杂度：$O(n)$

话说赛场上这种水题我居然没时间打了

清晰短小的代码：

xxxxxxxxxx
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define N 111111
#define INF 1e15
LL ind[N],ansp[N],g[N],f[N],nxt[N],d[N][3],lp[N],rp[N],ans=INF,n;
//ind[i]:第i个点的度
//ansp[]:方案
//g[x]:第x个点的颜色
//f[p]:链上第p个点的颜色
//nxt[i]:链上第i个点的下一个节点
//lp[i],rp[i]:第i个点的两个出边指向的点
//ans:答案
void search(int x,LL cost,int p){ //这是第x个点，当前花费为cost，这也是链上的第p个点
    if (nxt[x]==0){ //如果达到了链的另一个断点，则结束
        for (int i=0;i<3;++i){
            if (i!=f[p-1] && i!=f[p-2]){ //可以被使用的颜色。这里一定只有一个i满足要求
                f[p]=i;g[x]=i; //保存结果
                if (cost+d[x][i]<ans){ //如果方案更优
                    ans=cost+d[x][i]; //保存结果和方案
                    for (int j=1;j<=n;++j){
                        ansp[j]=g[j]+1; //由于保存的时候颜色按照0,1,2保存，所以应该加一
                    }
                }
            }
        }
        return;
    }
    if (p==1){ //如果这是链上的第一个点（链顶）
        for (int i=0;i<3;++i){ //分别枚举3种颜色
            f[p]=i;g[x]=i;
            search(nxt[x],cost+d[x][i],p+1);
        }
    }else if (p==2){ //如果这是链上的第二个点
        for (int i=0;i<3;++i){ //分别枚举可用的2种颜色，其中一个将被if语句过滤
            if (i!=f[1]){
                f[p]=i;g[x]=i;
                search(nxt[x],cost+d[x][i],p+1);
            }
        }
    }else{ //如果是其他的点
        for (int i=0;i<3;++i){
            if (i!=f[p-1] && i!=f[p-2]){ //这里一定只有一个i满足要求
                f[p]=i;g[x]=i;
                search(nxt[x],cost+d[x][i],p+1);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false); //读入优化
    cin>>n;
    for (int i=1;i<=n;++i) cin>>d[i][0];
    for (int i=1;i<=n;++i) cin>>d[i][1];
    for (int i=1;i<=n;++i) cin>>d[i][2];
    for (int i=1;i<n;++i){
        int x,y;cin>>x>>y;
        ind[x]++;ind[y]++; //度
        if (ind[x]>=3 || ind[y]>=3){ //这不是链，输出-1
            puts("-1");return 0;
        }
        if (lp[x]==0) lp[x]=y; else rp[x]=y; //由于度只有2，所以无需使用链向星，只要将两个出边分别指向对应的点即可
        if (lp[y]==0) lp[y]=x; else rp[y]=x; 
    }
    int root; //链的顶端
    for (int i=1;i<=n;++i){ //寻找链顶
        if (ind[i]==1){
            root=i;break; 
        }
    }
    int now=lp[root],pre=root;
    nxt[root]=now; //nxt数组记录每个节点后面的节点
    while (true){ //将lp和rp的信息转化为nxt的信息
        if (ind[now]==1) break;    
        if (lp[now]!=pre) nxt[now]=lp[now]; else nxt[now]=rp[now]; //判定下一个节点是哪个指针指向的
        pre=now;now=nxt[now]; //继续转化
    }
    search(root,0,1); //运行
    cout<<ans<<endl; //输出答案
    for (int i=1;i<n;++i){ //输出方案
        cout<<ansp[i]<<" ";
    }
    cout<<ansp[n]<<endl;
    return 0;
}

$389ms$