题目链接：见这里 题意：给了一颗树，要让每个连起来的(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;}新闻热点
疑难解答
