Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   10010
#define MAXV   20
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
vector<int> g[MAX];
int f[MAX][MAXV+7];
int p[MAX],r[MAX];
int n;
void loadtree(void) {
    scanf("%d",&n);
    REP(zz,n-1) {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
}
void dfs(int u) {
    FOR(i,1,MAXV) f[u][i]=i;
    FORE(it,g[u]) if (*it!=p[u]) {
        int v=*it;
        p[v]=u;
        dfs(v);
        FOR(i,1,MAXV) {
            int t=-1;
            FOR(j,1,MAXV) if (i!=j && (t<0 || f[v][t]>f[v][j])) t=j;
            f[u][i]+=f[v][t];
        }
    }
}
void trace(int u,int c) {
    r[u]=c;
    FORE(it,g[u]) if (*it!=p[u]) {
        int v=*it;
        int t=-1;
        FOR(i,1,MAXV) if (i!=c && (t<0 || f[v][t]>f[v][i])) t=i;
        trace(v,t);
    }
}
void process(void) {
    dfs(1);
    int j=1;
    FOR(i,1,MAXV) if (f[1][j]>f[1][i]) j=i;
    trace(1,j);
    printf("%d\n",f[1][j]);
    FOR(i,1,n) printf("%d\n",r[i]);
}
int main(void) {
    loadtree();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include "stdio.h"
#include "iostream"
#include "vector"

using namespace std;

#define maxc 30

int n;
vector<vector<int> > ke;
int f[10001][maxc+1];
int father[10001], la[10001];

void nhap() {
    int u,v;
    scanf("%d",&n);
    ke.resize(n+1);
    for(int i=1;i<n;++i) {
        scanf("%d%d",&u,&v);
        ke[u].push_back(v);
        ke[v].push_back(u);
    }    
}

void dfs(int i) {
    for(vector<int>::iterator p=ke[i].begin();p!=ke[i].end();++p)
        if(*p!=father[i]) {
            father[*p]=i;
            dfs(*p);
        }    
    for(int k=1;k<=maxc;++k) {
        f[i][k]=k;
        for(vector<int>::iterator p=ke[i].begin();p!=ke[i].end();++p) if(*p!=father[i]) {
            int fmin=1000000000;
            for(int t=1;t<=maxc;++t) if(t!=k) fmin<?=f[*p][t];
            f[i][k]+=fmin;
        }    
    }    
}    

void truyvet(int i,int k) {
    la[i]=k;
    for(vector<int>::iterator p=ke[i].begin();p!=ke[i].end();++p) if(*p!=father[i]) {
        int fmin=1000000000,tmin=-1;
        for(int t=1;t<=maxc;++t) if(t!=k && fmin>f[*p][t]) {
            fmin=f[*p][t];
            tmin=t;
        }    
        truyvet(*p,tmin);
    }    
}    

void xuly() {
    dfs(1);
    int fmin=1000000000,kmin=-1;
    for(int k=1;k<=maxc;++k) {
        if(f[1][k]<fmin) {
            fmin=f[1][k];
            kmin=k;
        }    
    }
    truyvet(1,kmin);
    printf("%d\n",f[1][kmin]);
    for(int i=1;i<=n;++i) printf("%d\n",la[i]);
}

int main() {
    nhap();
    xuly();
    return 0;
}