C++ 解法, 执行用时: 23ms, 内存消耗: 3980KB, 提交时间: 2021-11-12

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
//邻接表 双向边模式存储树
int nxt[N*2],val[N*2],head[N],lh;//全局变量均默认初始化为0
void push(int a,int b){
    nxt[++lh]=head[a];head[a]=lh;
    val[lh]=b;return;
}
int main(){
    int n,u,v;cin>>n;
    //输入的同时使用并查集校验
    int r1,r2;
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&u,&v);
        push(u,v);push(v,u);
    }
    //树形dp
    int dp[N]={};//约定值为子节点里1节点的个数
    //1节点有且仅有1个 本节点为类型2
    //1个以上：矛盾
    //0个：本节点为类型1 从下往上检查
    //根节点不能为类型1 额外处理
    struct D{int father,cur;bool recflag;}st[N];int sth=0;
    st[sth++]={0,1,0};
    while(sth){
        D&cur=st[sth-1];
        if(!cur.recflag){
            cur.recflag=1;
            for(int i=head[cur.cur];i!=0;i=nxt[i])
                if(val[i]!=cur.father)
                    st[sth++]={cur.cur,val[i],0};
        }else{
            if(dp[cur.cur]>1){
                printf("-1");return 0;
            }
            if(dp[cur.cur]==0)
                dp[cur.father]++;
            sth--;
        }
    }
    if(dp[1]==0){printf("-1");return 0;}
    //染色
    struct D2{int father,cur;}st2[N];sth=0;
    char color[N]={'B'};
    st2[sth++]={0,1};
    while(sth){
        const D2 cur=st2[--sth];
        if(!dp[cur.cur])color[cur.cur]=color[cur.father];
        else if(color[cur.father]=='R')color[cur.cur]='B';
        else color[cur.cur]='R';
        for(int i=head[cur.cur];i!=0;i=nxt[i])
                if(val[i]!=cur.father)
                    st2[sth++]={cur.cur,val[i]};
    }
    printf("%s",color+1);
    return 0;
}

C++ 解法, 执行用时: 25ms, 内存消耗: 8312KB, 提交时间: 2022-05-18

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1E5 + 10;
ll read() {
    ll a = 0;
    char b = 1, c;
    do
        if ((c = getchar()) == 45) b = -1;
    while (c < 48 || c > 57);
    do
        a = (a << 3) + (a << 1) + (c & 15);
    while ((c = getchar()) > 47 && c < 58);
    return a * b;
}
int head[N], nex[N << 1], to[N << 1];
int cnt;
int fri[N];
bitset<N> b;
void add(int u, int v) {
    nex[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

void dfs1(int x, int f) {
    for (int i = head[x]; i; i = nex[i]) {
        int t = to[i];
        if (t == f) continue;
        dfs1(t, x);
        if (!fri[x] && !fri[t]) {
            fri[x] = t;
            fri[t] = x;
        }
    }
}

void dfs2(int x, int f) {
    for (int i = head[x]; i; i = nex[i]) {
        int t = to[i];
        if (t == f) continue;
        b[t] = t == fri[x] ? b[x] : !b[x];
        dfs2(t, x);
    }
}

int main() {
    int n = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        add(u, v);
        add(v, u);
    }
    dfs1(1, 0);
    if (!*min_element(fri + 1, fri + 1 + n)) {
        puts("-1");
        return 0;
    }
    dfs2(1, 0);
    for (int i = 1; i <= n; ++i) putchar(b[i] ? 'R' : 'B');
}

C++ 解法, 执行用时: 28ms, 内存消耗: 7312KB, 提交时间: 2021-11-27

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n,tag,f[N],col[N];
int head[N],ver[N],nxt[N],tot;
inline void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
inline void dfs(int x,int fa)
{
    if(tag==-1)return;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        if((!f[x])&&(!f[y])){
            f[x]=y;f[y]=x;
        }
        else if((f[x])&&(!f[y])){
            tag=-1;return;
        }
    }
}
inline void sol(int x,int fa)
{
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa)continue;
        if(f[x]==y){
            col[y]=col[x];
        }else col[y]=1-col[x];
        sol(y,x);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
//     for(int i=1;i<=n;i++)printf("f[%d]=%d\n",i,f[i]);
    if(!f[1])tag=-1;
    if(tag==-1)printf("-1");
    else{
         sol(1,0);
        for(int i=1;i<=n;i++){
            if(col[i])putchar('R');
            else putchar('B');
        }
    }
    return 0;
}

C++ 解法, 执行用时: 34ms, 内存消耗: 7356KB, 提交时间: 2021-12-30

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

C++ 解法, 执行用时: 37ms, 内存消耗: 3996KB, 提交时间: 2022-05-08

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int nxt[N * 2], val[N * 2], head[N], lh;
void push(int a, int b) {
    nxt[++lh] = head[a];
    head[a] = lh;
    val[lh] = b;
    return;
}
int main() {
    int n, u, v;
    cin >> n;
    int r1, r2;
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &u, &v);
        push(u, v);
        push(v, u);
    }
    int dp[N] = {};
    struct D {
        int father, cur;
        bool recflag;
    } st[N];
    int sth = 0;
    st[sth++] = {0, 1, 0};
    while (sth) {
        D& cur = st[sth - 1];
        if (!cur.recflag) {
            cur.recflag = 1;
            for (int i = head[cur.cur]; i != 0; i = nxt[i])
                if (val[i] != cur.father)
                    st[sth++] = {cur.cur, val[i], 0};
        } else {
            if (dp[cur.cur] > 1) {
                printf("-1");
                return 0;
            }
            if (dp[cur.cur] == 0)
                dp[cur.father]++;
            sth--;
        }
    }
    if (dp[1] == 0) {
        printf("-1");
        return 0;
    }
    struct D2 {
        int father, cur;
    } st2[N];
    sth = 0;
    char color[N] = {'B'};
    st2[sth++] = {0, 1};
    while (sth) {
        const D2 cur = st2[--sth];
        if (!dp[cur.cur])color[cur.cur] = color[cur.father];
        else if (color[cur.father] == 'R')color[cur.cur] = 'B';
        else color[cur.cur] = 'R';
        for (int i = head[cur.cur]; i != 0; i = nxt[i])
            if (val[i] != cur.father)
                st2[sth++] = {cur.cur, val[i]};
    }
    printf("%s", color + 1);
    return 0;
}