题解 | #红和蓝#

可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解：

• 若当前节点x与父节点颜色相同，那么它的子节点子树大小必须为偶数，子节点颜色和x不同。

• 若当前节点x与父节点颜色不同，那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。x的“奇数大小子树”的那个子节点颜色和x相同，其他都和x不同。

#include<bits/stdc++.h> using namespace std; vector<int>g[200020]; int dp[2

00020]; int su(int x,int pr){ int i,sum=1; for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){
            sum+=su(g[x][i],x);
        }
    } return dp[x]=sum;
} char out[200020]; int jud=0; char f(char c){ if(c=='R')return 'B'; return 'R';
} void dfs(int x,int pr,char c){ if(jud)return;
    out[x]=c; int cnt=0,i; for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){
            cnt+=dp[g[x][i]]&1;
        }
    } if(out[x]==out[pr]){ if(cnt!=0){jud=1;return;} for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){
                dfs(g[x][i],x,f(c));
            }
        }
    } else { if(cnt!=1){jud=1;return;} for(i=0;i<g[x].size();i++){ if(g[x][i]!=pr){ if(dp[g[x][i]]&1)dfs(g[x][i],x,c); else dfs(g[x][i],x,f(c));
            }
        }
    }
} int main(){ int n,i; cin>>n; for(i=0;i<n-1;i++){ int x,y; cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dp[1]=su(1,-1);
    out[0]='B';
    dfs(1,0,'R'); if(jud)cout<<-1; else for(i=1;i<=n;i++)cout<<out[i];
}  }