CTREE - Tô màu nhỏ nhất

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
const int N = 10004;
const int oo = trunc(1e9);
using namespace std;
int F[N][4], color[N], n;
vector<int> a[N], child[N];
bool visit[N];

void DFS(int u) {
    visit[u] = true;
    for(int i=0; i<a[u].size(); i++) {
        int v = a[u][i];
        if (!visit[v]) {
            child[u].push_back(v);
            DFS(v);
        }
    }
}

int Min(int i, int c) {
    int mi = oo;
    for(int j=1; j<=3; j++)
        if (j != c) mi = min(mi, F[i][j]);
    return mi;
}

void DP(int u) {
    if (child[u].size() == 0) {
        for(int i=1; i<=3; i++)
            F[u][i] = i;
        return;
    }
    for(int i=0; i<child[u].size(); i++) {
        int v = child[u][i];
        DP(v);
    }
    for(int i=1; i<=3; i++) {
        F[u][i] = i;
        for(int j=0; j<child[u].size(); j++) {
            int v = child[u][j];
            F[u][i] += Min(v, i);
        }
    }
}

void Play(int u, int c) {
    color[u] = c;
    for(int i=0; i<child[u].size(); i++) {
        int v = child[u][i];
        int mi = oo, next;
        for(int j=1; j<=3; j++)
        if (j != c && F[v][j] < mi) {
            mi = F[v][j]; next = j;
        }
        Play(v, next);
    }
}

int main()
{
    //freopen("CTREE.inp", "r", stdin);
    scanf("%d\n", &n); int u, v;
    for(int i=1; i<n; i++) {
        scanf("%d %d\n", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    DFS(1);
    DP(1);
    int root = 1;
    if (F[1][2] < F[1][root]) root = 2;
    if (F[1][3] < F[1][root]) root = 3;
    Play(1, root);
    printf("%d\n", F[1][root]);
    for(int i=1; i<=n; i++) printf("%d\n", color[i]);
    return 0;
}

Download