题目大意就是给一棵树，然后任意3个相连的点都可以组成一个三元组，要求任意一个三元组里的3个点的颜色两两不相同，然后问需要的最少颜色种类，还有每个点的染色情况。
首先可以知道选取一个点的颜色的时候，这个点的颜色不能和它的父节点和父节点的父节点颜色相同，此外还不能和它的兄弟节点的颜色相同，知道这些就可以写了。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+10; struct node { int v,nxt; }e[2*maxn]; int head[maxn],col[maxn],ans,n,cnt; void addedge(int u,int v) { e[cnt].v=v; e[cnt].nxt=head[u]; head[u]=cnt++; e[cnt].v=u; e[cnt].nxt=head[v]; head[v]=cnt++; } void dfs(int now,int fa)//now当前节点，fa表示当前节点的父节点 { int tmp=1; for(int i=head[now];i!=-1;i=e[i].nxt)//遍历now的儿子节点 { int v=e[i].v; if(v!=fa) { while(tmp==col[now]||tmp==col[fa])从颜色编号最小开始找可用颜色，因为题目要求使用最少的颜色 tmp++; col[v]=tmp; ans=max(ans,tmp); dfs(v,now); tmp++;//在这里自增是为了防止now节点的多个儿子节点用同一种颜色， } } } int main() { std::ios::sync_with_stdio(false); memset(head,-1,sizeof(head)); memset(col,0,sizeof(col)); ans=cnt=0; cin>>n; for(int i=1;i<=n-1;i++) { int u,v; cin>>u>>v; addedge(u,v); } col[1]=1; ans=1; dfs(1,0); cout<<ans<<endl; for(int i=1;i<=n;i++) cout<<col[i]<<" "; cout<<endl; return 0; }
