目錄

• 題目
• 官方題解：
• 百度翻譯
• 題解
• ac代碼

題目

給多組兩頂點連接，得到的圖任意三個頂點都是不同的顏色，，給出各頂點染三種顏色的花費，問各店如何染，滿足條件情況下，使得花費最少；

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) such that x≠y,y≠z,x≠z, x is connected by an edge with yy, and yy is connected by an edge with zz. 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 nn (3≤n≤100000)— the number of vertices.

The second line contains a sequence of integers c1,1,c1,2,…,c1,n(1≤c1,i≤10${}^9$), where c1,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,n)(1≤c2,i≤10${}^9$), where c2,iis 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,n(1≤c3,i≤10${}^9$), 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 ujuj and vjvj (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.

Otherwise, print the minimum cost of a good painting in the first line. In the second line print nn integers b1,b2,…,bn (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 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.

官方題解：

百度翻譯

關鍵的觀察是，如果我們確定了兩個相鄰頂點xx和yy的顏色，那么與xx或yy相鄰的任何頂點的顏色只能是6-cx-cy。因此，我們可以確定任何邊的端點的顏色（有6種可能這樣做），然后對所有其他頂點進行遍歷，然后再做一次遍歷來檢查我們是否有一幅好畫。

為了避免檢查我們得到的畫是否好（這可能很難編碼），我們可以使用這樣一個事實：對于每個頂點，其所有相鄰頂點的顏色應該彼此不同，并且與我們固定的頂點的顏色不同。所以，如果某個頂點的度數大于等于3，那么就沒有好的畫；否則我們得到的畫就是好的，因為圖是一個鏈。

題解

（1）如果滿足條件，則一個頂點上最多只有兩條邊，所以該各頂點可連接后是一條鏈，所以判斷若有點超過兩個鏈接，則判為不存在；
（2）由于要找出最小花費的染色方案，則需遍歷所有可能存在染色情況，找出最優方案。若為一條鏈，且只有三種顏色，找出頭或尾（只有一個連接）確定兩個顏色即可確定另一個，所以共有三種情況。
（3）注意一下，因為雙向的，所以用過某條邊之后，不能再用，否則會造成錯誤，鏈中存在環。

ac代碼

#include<stdio.h> #include<string.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int M=1e5+10; int n; int a[4][M]; vector<int> e[M];///記錄某點連接的的其他點 ll s; int t[M], c[M], dp[M];///c[M]為（1~n）個點的顏色，t[M]是成鏈每一步的顏色，記錄最優解各點的顏色 void dfs(int cur, int par, int step)///cur當前點，par之前出現的點（防止雙向成環），鏈上的第幾個點 {if(step>=3)t[step] = 6-t[step-1]-t[step-2];c[cur] = t[step];s+=a[t[step]][cur];for(int i=0; i<e[cur].size(); i++)///i從零開始{int nxt = e[cur][i];if(nxt==par)///防止雙向成環continue;dfs(nxt, cur, step+1);} } int main() {scanf("%d", &n);for(int i=1; i<=3; i++)for(int j=1; j<=n; j++)scanf("%d", &a[i][j]);for(int i=1; i<n; i++){int x, y;scanf("%d%d", &x, &y);e[x].push_back(y);e[y].push_back(x);}bool flag = true;int st = 1;for(int i=1; i<=n; i++){if (e[i].size() > 2)flag = false;if (e[i].size() == 1)st = i;}if (!flag){puts("-1");return 0;}ll ans =-1;///長整形，不能用0x3f3f3f3f來代表無窮大故為-1for(t[1] = 1; t[1]<=3; t[1]++)for(t[2] = 1; t[2]<=3; t[2]++){if(t[2]==t[1])continue;s = 0;dfs(st, 0, 1);if (ans > s||ans<0){ans = s;for(int i=1; i<=n; i++)dp[i] = c[i];}}printf("%lld\n", ans);for(int i=1; i<n; i++)printf("%d ", dp[i]);printf("%d\n",dp[n]);return 0; }

總結

以上是生活随笔為你收集整理的Paint the Tree CodeForces - 1244D（看似是树，其实是条链）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。