題目鏈接：見這里 題意：給了一顆樹，要讓每個連起來的(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]);新聞熱點
疑難解答
