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 flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int n, subtree[100100], par[100100], region[100100], sum[100100];
vector <int> a[100100];

pair <int,int> partition(vector < pair<int,int> > &num)
{
    int L = 0, R = int(num.size()) - 1; 

    sum[0] = num[0].first;
    for (int i = 1; i <= R; i++) sum[i] = sum[i - 1] + num[i].first;

    int low = sum[R] / 3, high = sum[R] * 2 / 3;

    while (L < R)
    {
        int M = L + rand() % (R - L + 1);
        int sumRight = sum[R] - sum[M], sumLeft = sum[M] - (L ? sum[L - 1] : 0);

        if (low <= sumLeft && sumLeft <= high) return make_pair(L, M);
        if (low <= sumRight && sumRight <= high) return make_pair(M + 1, R);

        if (sumLeft >= sumRight) R = M;
        else L = M + 1;
    }

    return make_pair(L, R);
}

void dfs(int x, int par, int curRegion)
{
    region[x] = curRegion;
    for (int i = 0; i < int(a[x].size()); i++)
    {
        int y = a[x][i];
        if (y != par) dfs(y, x, curRegion);
    }
}

void solve(int x, vector < pair<int,int> > num)
{
    pair <int,int> u = partition(num);
    int L = u.first, R = u.second, sumLR = 0;
    vector < pair<int,int> > num2;

    for (int i = L; i <= R; i++) sumLR += num[i].first;

    for (int i = 0; i < int(num.size()); i++)
        if ((sumLR <= n / 2) ^ (i < L || i > R))
            region[num[i].second] = 1;
        else
            num2.push_back(num[i]);

    u = partition(num2);
    L = u.first; R = u.second;
    for (int i = 0; i < int(num2.size()); i++)
        if (L <= i && i <= R) region[num2[i].second] = 2;
        else region[num2[i].second] = 3;

    for (int i = 0; i < int(a[x].size()); i++)
    {
        int y = a[x][i];
        dfs(y, x, region[y]);
    }

    for (int i = 1; i <= n; i++) printf("%d%c", region[i], (i == n ? '\n' : ' '));
}

void visit(int x)
{
    int ok = 1;
    subtree[x] = 1;
    vector < pair<int,int> > num;

    for (int i = 0; i < int(a[x].size()); i++)
    {
        int y = a[x][i];
        if (y == par[x]) continue;
        par[y] = x;
        visit(y);
        subtree[x] += subtree[y];
        if (subtree[y] * 2 > n) ok = 0;
        num.push_back(make_pair(subtree[y], y));
    }

    if (ok && (n - subtree[x]) * 2 <= n && a[x].size() >= 3) 
    {
        if (par[x]) num.push_back(make_pair(n - subtree[x], par[x]));
        solve(x, num);
        exit(0);
    }

    num.clear();
}

int main()
{
    int x, y;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    visit(1);
    puts("-1");
}

Code mẫu của happyboy99x

#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;

#define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 100000;
vector<vector<int> > g;
int res[N], n, r[N];

template<class T> int size(const T &t) { return (int) t.size(); }

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

void fill(int u, int p, int color) {
    res[u] = color;
    TR(g[u], v) if(*v != p)
        fill(*v, u, color);
}

void print(int u) {
    for(int i = 0; i < n; ++i) {
        if(i) printf(" ");
        if(res[i] != 0) printf("%d", res[i]);
        else printf("%d", i == u ? 0 : 3);
    }
    printf("\n");
    exit(EXIT_SUCCESS);
}

void dfs(int u, int p) {
    r[u] = 1;
    vector<int> child;
    TR(g[u], v) if(*v != p) {
        child.push_back(*v);
        dfs(*v, u);
        r[u] += r[*v];
    }
    if(p != -1 && size(child) > 1 && n-r[u] <= n/2) {
        int left = 0, right = 0, sum = 0;
        bool ok = true;
        while(sum < 1 || sum > n/2 || r[u]-1-sum < 1 || r[u]-1-sum > n/2) {
            if((sum < 1 || r[u]-1-sum > n/2) && right < size(child)) sum += r[child[right++]];
            else if((sum > n/2 || r[u]-1-sum < 1) && left < size(child)) sum -= r[child[left++]];
            else {
                ok = false;
                break;
            }
        }
        if(ok) {
            for(int i = 0; i < size(child); ++i)
                if(left <= i && i < right) fill(child[i], u, 1);
                else fill(child[i], u, 2);
            print(u);
        }
    }
}

int main() {
    enter();
    for(int u = 0; u < n; ++u)
        if(size(g[u]) == 1) {
            dfs(u, -1);
            break;
        }
    printf("-1\n");
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 100005;
using namespace std;
VI a[N];
vector<II> ss;
int ans[N], par[N], s[N];
int n, cut;

void dfs(int u) {
    s[u] = 1;
    TR(v, a[u])
    if (*v != par[u]) {
        par[*v] = u;
        dfs(*v);
        s[u] += s[*v];
    }
}

void write(int u) {
    TR(v, a[u])
    if (ans[*v] == 0 && *v != cut) {
        ans[*v] = ans[u];
        write(*v);
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int u, v;
    FOR(i, 1, n) {
        cin >> u >> v;
        a[u].PB(v); a[v].PB(u);
    }
    dfs(1);
    bool found = 0;
    FOR(i, 1, n) {
        ss.clear(); bool ok = 1;
        TR(j, a[i]) {
            if (*j == par[i]) ss.PB(MP(s[1] - s[i], *j));
            else ss.PB(MP(s[*j], *j));
            if (ss[SZ(ss) - 1].X > n / 2) {
                ok = 0; break;
            }
        }
        if (ok && SZ(ss) > 2) {
            cut = i; int cnt = SZ(ss);
            sort(ALL(ss), greater<II>());
            int m = n / 2;
            FOR(j, 0, SZ(ss)) if (ss[j].X <= m && cnt > 2) {
                m -= ss[j].X; ans[ss[j].Y] = 1; cnt--;
            }
            m = n / 2;
            FOR(j, 0, SZ(ss)) if (ss[j].X <= m && ans[ss[j].Y] == 0 && cnt > 1) {
                m -= ss[j].X; ans[ss[j].Y] = 2; cnt--;
            }
            FOR(j, 0, SZ(ss)) if (ans[ss[j].Y] == 0) ans[ss[j].Y] = 3;
            found = 1;
            break;
        }
    }
    if (!found) {cout << -1; return 0;}
    TR(u, a[cut]) write(*u);
    REP(i, 1, n) cout << ans[i] << ' ';
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
using namespace std;

const int MN = 100111;

int n, father[MN], sz[MN];
vector<int> ke[MN];

void dfs1(int u, int fu) {
    father[u] = fu;
    sz[u] = 1;

    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (v == fu) continue;

        dfs1(v, u);
        sz[u] += sz[v];
    }
}

pair<int,int> x[MN];
int cur[4];
int color[MN];

void dfs2(int u, int fu, int c) {
    color[u] = c;
    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (v == fu) continue;

        dfs2(v, u, c);
    }
}

bool check(int u) {
    if (ke[u].size() < 3) return false;

    memset(cur, 0, sizeof cur);
    int now = 0;
    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (v == father[u]) x[++now] = make_pair(sz[1] - sz[u], v);
        else x[++now] = make_pair(sz[v], v);
    }

    sort(x+1, x+now+1);

    FORD(i,now,1) {
        int good;
        int best = min(cur[1], min(cur[2], cur[3]));
        if (cur[1] == best) good = 1;
        else if (cur[2] == best) good = 2;
        else good = 3;

        cur[good] += x[i].first;
        color[x[i].second] = good;

        if (cur[good] > (n >> 1)) return false;
    }

    REP(i,ke[u].size()) {
        int v = ke[u][i];
        dfs2(v, u, color[v]);
    }

    color[u] = 0;
    FOR(i,1,n) printf("%d ", color[i]); puts("");
    return true;
}

int main() {
    while (scanf("%d", &n) == 1) {
        FOR(i,1,n) ke[i].clear();
        FOR(i,2,n) {
            int u, v; scanf("%d%d", &u, &v);
            ke[u].push_back(v);
            ke[v].push_back(u);
        }
        memset(father, -1, sizeof father);
        dfs1(1, -1);

        // FOR(i,1,n) cout << father[i] << ' '; cout << endl;
        // FOR(i,1,n) cout << sz[i] << ' '; cout << endl;

        bool found = false;
        FOR(u,1,n) {
            if (check(u)) {
                found = true;
                break;
            }
        }
        if (!found) puts("-1");
    }
    return 0;
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
#define MAX   100100
#define x   first
#define y   second
using namespace std;
typedef pair<int,int> ii;
vector <int> g[MAX];
int p[MAX];
int c[MAX];
int nc[MAX];
int a[MAX];
int r[MAX];
int n;
vector<ii> can;
int s[7];
void loadgraph(void) {
    scanf("%d",&n);
    int i,u,v;
    for (i=1;i<n;i=i+1) {   
        scanf("%d",&u);
        scanf("%d",&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (i=1;i<=n;i=i+1) c[i]=0;
    p[1]=-1;
    c[1]=1; 
}
void DFS(int u) {
    int i;
    nc[u]=1;
    for (i=0;i<g[u].size();i=i+1) 
        if (c[g[u][i]]==0) {
            c[g[u][i]]=1;
            p[g[u][i]]=u;
            DFS(g[u][i]);
            nc[u]+=nc[g[u][i]];
        }
}
int min(int x,int y,int z) {
    if ((x<=y) && (x<=z)) return(x);
    if ((y<=x) && (y<=z)) return(y);
    if ((z<=x) && (z<=y)) return(z);
}
int max(int x,int y,int z) {
    if ((x>=y) && (x>=z)) return(x);
    if ((y>=x) && (y>=z)) return(y);
    if ((z>=x) && (z>=y)) return(z);
}
int mini(void) {
    int m=min(s[0],s[1],s[2]);
    int i;
    for (i=0;i<3;i=i+1)
        if (s[i]==m) return (i);
}
int maxi(void) {
    int m=max(s[0],s[1],s[2]);
    int i;
    for (i=0;i<3;i=i+1)
        if (s[i]==m) return (i);
}
bool cmp(ii a,ii b) {
    return (a>b);
}
bool test(int u) {
    if (g[u].size()<3) return (false);
    can.clear();
    int i,j,t;
    t=0;    
    for (i=0;i<g[u].size();i=i+1)
        if (g[u][i]!=p[u]) {
            if (nc[g[u][i]]>n/2) return (false);
            can.push_back(ii(nc[g[u][i]],g[u][i]));
            t+=nc[g[u][i]];
        }
    if (n-1-t>n/2) return (false);
    if (p[u]>0) can.push_back(ii(n-1-t,p[u]));
    sort(can.begin(),can.end(),cmp);
    for (i=1;i<=n;i=i+1) r[i]=-1;
    s[0]=0;s[1]=0;s[2]=0;
    int mx,mn,ma,ix,in,ia;
    for (i=0;i<can.size();i=i+1) {
        mx=max(s[0],s[1],s[2]);
        mn=min(s[0],s[1],s[2]);
        ma=s[0]+s[1]+s[2]-mx-mn;
        ix=maxi();
        in=mini();
        ia=3-maxi()-mini();
        if (mn+can[i].x>n/2) return  (false);
        if ((can.size()-i<3) && (mn==0)) {
            s[in]+=can[i].x;
            r[can[i].y]=in+1;
            continue;
        }
        if (mx+can[i].x<=n/2) {
            s[ix]+=can[i].x;
            r[can[i].y]=ix+1;
            continue;
        }
        if (ma+can[i].x<=n/2) {
            s[ia]+=can[i].x;
            r[can[i].y]=ia+1;
            continue;
        }
        if (mn+can[i].x<=n/2) {
            s[in]+=can[i].x;
            r[can[i].y]=in+1;
            continue;
        }
    }
    return (true);
}
void fill(int u,int val) {
    r[u]=val;
    int i;
    for(i=0;i<g[u].size();i=i+1)
        if (g[u][i]!=p[u]) fill(g[u][i],val);
}
void process(void) {
    DFS(1);
    int i,j;
    for (i=1;i<=n;i=i+1)
        if (test(i)) {
            for (j=0;j<g[i].size();j=j+1)   
                if (g[i][j]!=p[i]) fill(g[i][j],r[g[i][j]]);
            r[i]=0;
            for (j=1;j<n;j=j+1) {
                if (r[j]<0) printf("%d ",r[p[i]]);
                else printf("%d ",r[j]);
            }
            if (r[n]<0) printf("%d",r[p[i]]);
            else printf("%d",r[n]);
            exit(0);
        }
    printf("-1");
}
int main(void) {
    loadgraph();
    process();
    return 0;
}