测试详情

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <vector>
#define debug cout<<"ok"<<endl;
#define ll long long
#define maxn 2000008
using namespace std;
int color[maxn],ans[maxn],cwhite,cblack;
vector<int> e[maxn];
int t1=1,t2=2,t3=3;
int i,j,n;
void add(int u,int v){
	e[u].push_back(v);
	e[v].push_back(u);
}
void dfs(int u,int fa){
	color[u]=!color[fa];
	if(color[u])cblack++;
	else cwhite++;
	for(int i=0;i<e[u].size();i++){
		if(i!=fa)dfs(i,u);
	}
}
void work1(){
	for(int i=1;i<=n;i++){
		if(color[i]==0){
			if(t1<=n)ans[i]=t1,t1+=3;
			else ans[i]=t3,t3+=3;
		}
		else{
			if(t2<=n)ans[i]=t2,t2+=3;
			else ans[i]=t3,t3+=3;
		}
	}
} 
void work2(){
	for(int i=1;i<=n;i++){
		if(color[i]==0){
			if(t1<=n)ans[i]=t1,t1+=3;
			else if(t2<=n)ans[i]=t2,t2+=3;
			else ans[i]=t3,t3+=3;
		}
		else
		ans[i]=t3,t3+=3;
	}
}
void work3(){
	for(int i=1;i<=n;i++){
		if(color[i]==1){
			if(t1<=n)ans[i]=t1,t1+=3;
			else if(t2<=n)ans[i]=t2,t2+=3;
			else ans[i]=t3,t3+=3;
		}
		else
			ans[i]=t3,t3+=3;
	}
}
int main()
{	
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	dfs(1,1);
	if(cwhite>n/3&&cblack>n/3)work1();
	else if(cblack<=n/3)work2();
	else if(cwhite<=n/3)work3();
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	cout<<endl;
	return 0;
}