题解 CF1244D 【Paint the Tree】

2019-10-14 19:17:06


观察可得如果能够成功染色,那么任何一个点的度数都不能超过3

那么,这个树就是一条链......

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,c[4][N],deg[N];
vector<int> e[N];
long long val[4][4];
int out[N];
long long dfs(int pos,int fa,int l1,int l2) //第一遍搜答案
{
    for (int i = 1;i <= 3;i++)
        if (i != l1 && i != l2)
        {
            if (e[pos].size() == 1) return c[i][pos];
            int nxt = e[pos][0];
            if (nxt == fa) nxt = e[pos][1];
            return c[i][pos] + dfs(nxt,pos,i,l1);
        }
    throw;
}
void print(int pos,int fa,int l1,int l2) //第二遍"打印"答案
{
    for (int i = 1;i <= 3;i++)
        if (i != l1 && i != l2)
        {
            out[pos] = i;
            if (e[pos].size() == 1) return;
            int nxt = e[pos][0];
            if (nxt == fa) nxt = e[pos][1];
            return print(nxt,pos,i,l1);
        }
}
int main ()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1;i <= 3;i++)
        for (int j = 1;j <= n;j++) cin >> c[i][j];
    int t1,t2;
    for (int i = 1;i < n;i++)
    {
        cin >> t1 >> t2;++deg[t1];++deg[t2];
        e[t1].push_back(t2);e[t2].push_back(t1);
    }
    int pos = 0,cnt = 0;
    for (int i = 1;i <= n;i++)
        if (deg[i] == 1) ++cnt,pos = i;
        else if (deg[i] > 2) {cout << -1 << endl;return 0;}
    if (cnt != 2) {cout << -1 << endl;return 0;}
    int nxt = e[pos][0],nn = nxt;
    if (e[nxt][0] == pos) nxt = e[nxt][1];else nxt = e[nxt][0];//获取链上的前2个点
    long long ans = LLONG_MAX;
    for (int i = 1;i <= 3;i++)
        for (int j = 1;j <= 3;j++)
            if (i != j)
                ans = min(ans,
                val[i][j] = dfs(nxt,nn,i,j) + c[j][pos] + c[i][nn]);//枚举前2个染什么,后面的都是确定的
    for (int i = 1;i <= 3 && !out[1];i++)
        for (int j = 1;j <= 3;j++)
            if (i != j && ans == val[i][j])
            {
                cout << ans << endl;
                out[pos] = j;out[nn] = i;
                print(nxt,nn,i,j);
                break;
            }
    for (int i = 1;i <= n;i++) cout << out[i] << ' ';
    return 0;
}