题目链接:见这里
题意:给了一颗树,要让每个连起来的(u, v, w)三个点的颜色不同,默认1点被染成颜色1,问最少多少种颜色可以完成,并输出每个点的颜色编号。
解法:贪心+DFS,直接记录一下,这个点的父亲的颜色,和这个点的父亲的父亲的颜色,只要颜色颜色和它们不同就可以用这个颜色更新当前这个点的颜色,染完这个点之后让颜色编号nowc++,使得每个点的其他儿子节点和它的颜色不同。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
struct edge{
    int v, nxt;
    edge(){}
    edge(int v, int nxt) : v(v), nxt(nxt) {}
}E[maxn*2];
int n, ans[maxn], head[maxn], edgecnt;
void init(){edgecnt = 0; memset(head, -1, sizeof(head));}
void addedge(int u, int v){
    E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++;
}
void dfs(int u, int fa){
    int nowc = 1;
    for(int i = head[u]; ~i; i = E[i].nxt){
        int v = E[i].v;
        if(v == fa) continue;
        while(ans[u] == nowc || ans[fa] == nowc) nowc++;
        ans[v] = nowc;
        nowc++;
        dfs(v, u);
    }
}
int main()
{
    init();
    int n;
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        int u, v; scanf("%d%d", &u, &v);
        addedge(u, v); addedge(v, u);
    }
    ans[1] = 1;
    dfs(1, 0);
    int maxc = 0;
    for(int i = 1; i <= n; i++) maxc = max(maxc, ans[i]);
    printf("%d\n", maxc);
    for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}