构造类问题往往都是由特殊到简单
而对于树形结构最特别的就是叶子
#include <bits/stdc++.h> using namespace std; int n, tot = 0; int head[100010]; struct ty { int t, next; }edge[200010]; int f[100010]; int col[100010]; int cnt = 0; bool boo = 1; void addedge(int x, int y) { edge[++tot].t = y; edge[tot].next = head[x]; head[x] = tot; } void dfs1(int x, int fa) { int son = 0; for (int i = head[x]; i != -1; i= edge[i].next) { if (edge[i].t == fa) continue; son++; dfs1(edge[i].t, x); } if (son == 0 || f[x] == 0) { if (f[fa] != 0) {boo = 0; return ;} f[x] = f[fa] = ++cnt; } } void dfs2(int x, int fa) { for (int i = head[x]; i != -1; i= edge[i].next) { if (edge[i].t == fa) continue; if (f[edge[i].t] == f[x]) col[edge[i].t] = col[x]; else col[edge[i].t] = col[x] ^ 1; dfs2(edge[i].t, x); } } int main() { memset(head, -1, sizeof(head)); memset(edge, -1, sizeof(edge)); scanf("%d", &n); for (int i =1; i < n; i++) { int x, y; scanf("%d%d", &x, &y); addedge(x, y); addedge(y, x); } dfs1(1, 0); if (f[0] != 0 || boo == 0) { printf("-1\n"); return 0; }javascript:void(0); col[1] = 1; dfs2(1, 0); for (int i = 1; i <= n;i++) { if (col[i] == 1) printf("R"); else printf("B"); } return 0; }