1244D - Paint the Tree - CodeForces Solution

#define _CRT_SECURE_NO_WARNINGS



#include <map>

#include <set>

#include <stack>

#include <ctime>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cctype>

#include <vector>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <cassert>

#include <fstream>

#include <iostream>

#include <algorithm>



using namespace std;



typedef long long LL;



inline char gc() {

	static const LL L = 233333;

	static char sxd[L], *sss = sxd, *ttt = sxd;

	if (sss == ttt) {

		ttt = (sss = sxd) + fread(sxd, 1, L, stdin);

		if (sss == ttt) {

			return EOF;

		}

	}

	return *sss++;

}



#ifdef ONLINE_JUDGE

#define dd c = gc()

#else

#define dd c = getchar()

#endif

inline char readalpha() {

	char dd;

	for (; !isalpha(c); dd);

	return c;

}



inline char readchar() {

	char dd;

	for (; c == ' '; dd);

	return c;

}



template <class T>

inline bool read(T& x) {

	bool flg = false;

	char dd;

	x = 0;

	for (; !isdigit(c); dd) {

		if (c == '-') {

			flg = true;

		} else if(c == EOF) {

			return false;

		}

	}

	for (; isdigit(c); dd) {

		x = (x << 1) + (x << 3) + (c ^ 48);

	}

	if (flg) {

		x = -x;

	}

	return true;

}

#undef dd



template <class T>

inline void write(T x) {

	if (x < 0) {

		putchar('-');

		x = -x;

	}

	if (x < 10) {

		putchar(x | 48);

		return;

	}

	write(x / 10);

	putchar((x % 10) | 48);

}



typedef long long LL;



typedef long long LL;



const int maxn = 100005;



int n;

int c[maxn][3];

LL f[maxn][3][3];

int g[maxn][3][3];



struct Edge {

	int to, nxt;

} e[maxn << 1];



int first[maxn];

int du[maxn];

int A[maxn];



inline void add_edge(int from, int to) {

	static int cnt = 0;

	du[from]++, du[to]++;

	e[++cnt].nxt = first[from];

	first[from] = cnt;

	e[cnt].to = to;

	e[++cnt].nxt = first[to];

	first[to] = cnt;

	e[cnt].to = from;

}



int bh[maxn];



inline void dfs(int now, int fa) {

	static int cnt = 0;

	bh[++cnt] = now;

	for (int i = first[now]; i; i = e[i].nxt) {

		int to = e[i].to;

		if (to != fa) {

			dfs(to, now);

		}

	}

}



int main() {

	read(n);

	for (int i = 0; i < 3; ++i) {

		for (int j = 1; j <= n; ++j) {

			read(c[j][i]);

		}

	}

	for (int i = 1; i < n; ++i) {

		int x, y;

		read(x), read(y);

		add_edge(x, y);

	}

	int dd = 0;

	for (int i = 1; i <= n; ++i) {

		if (du[i] > 2) {

			puts("-1");

			return 0;

		} else if (du[i] == 1) {

			dd = i;

		}

	}

	dfs(dd, 0);

//	for (int i = 1; i <= n; ++i) {

//		cout << bh[i] << ' ';

//	}

//	cout << endl;

	memset(f, 0x3f, sizeof(f));

	for (int i = 0; i < 3; ++i) {

		for (int j = 0; j < 3; ++j) {

			if (i != j) {

				f[2][j][i] = c[bh[1]][i] + c[bh[2]][j];

				g[2][j][i] = 0;

			}

		}

	}

//	for (int i = 0; i < 3; ++i) {

//		for (int j = 0; j < 3; ++j) {

//			cout << f[2][i][j] << ' ';

//		}

//		cout << endl;

//	}

//	cout << endl;

	for (int i = 3; i <= n; ++i) {

		for (int j = 0; j < 3; ++j) {

			for (int k1 = 0; k1 < 3; ++k1) {

				for (int k2 = 0; k2 < 3; ++k2) {

					if (j != k1 && k1 != k2 && k2 != j) {

						if (f[i][j][k1] > f[i - 1][k1][k2] + c[bh[i]][j]) {

							f[i][j][k1] = f[i - 1][k1][k2] + c[bh[i]][j];

							g[i][j][k1] = k2;

						}

					}

				}

//				cout << f[i][j][k1] << ' ';

			}

//			cout << endl;

		}

//		cout << endl;

	}

	LL a1 = 0, a2 = 0, ans = 0x3f3f3f3f3f3f3f3fll;

	for (int i = 0; i < 3; ++i) {

		for (int j = 0; j < 3; ++j) {

			if (ans > f[n][i][j]) {

				a1 = i, a2 = j;

				ans = f[n][i][j];

			}

		}

	}

	printf("%lld\n", ans);

	for (int i = n; i; --i) {

		A[bh[i]] = a1;

		int T = g[i][a1][a2];

		a1 = a2;

		a2 = T;

	}

	for (int i = 1; i <= n; ++i) {

		printf("%d ", A[i] + 1);

	}

	return 0;

}