【2021寒假集训营第一场】C-红和蓝

构造类问题往往都是由特殊到简单
而对于树形结构最特别的就是叶子

#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;
}