思路
由每个红点周围有且仅有一个红点,每个蓝点周围有且仅有一个蓝点可得,如果叶子结点为一种颜色时,它的周围只有其父亲结点,所以父亲结点和它同色。
根据上述我们可以进行dfs,从下到上两两配对,存在一个没有与之配对的结点说明不存在此解
配对完成后在进行一遍dfs经行染色,如果是匹配的染同一颜色,否则染不同颜色。
代码
// Problem: 红和蓝 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9981/C // Memory Limit: 524288 MB // Time Limit: 4000 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor) #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=100010; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); int col[N]; int f[N]; vector<int> g[N]; void dfs1(int u,int fa){ for(int v:g[u]){ if(v==fa) continue; dfs1(v,u); if(!f[u]&&!f[v]){ f[u]=v; f[v]=u; } } } void dfs2(int u,int fa){ for(int v:g[u]){ if(v==fa) continue; if(f[u]==v) col[v]=col[u]; else col[v]=col[u]^1; dfs2(v,u); } } void solve(){ int n;cin>>n; rep(i,1,n-1){ int u,v;cin>>u>>v; g[u].pb(v);g[v].pb(u); } dfs1(1,0); rep(i,1,n){ if(!f[i]){ cout<<"-1\n"; return; } } col[1]=1; dfs2(1,0); rep(i,1,n){ if(col[i]) cout<<"R"; else cout<<"B"; } } int main(){ ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) solve(); return 0; }