Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int main() {
- int t;
- cin>>t;
- while(t--){
- int n;
- cin>>n;
- vector<vector<int>> tree(n);
- for(int i=0; i<n-1; i++)
- {
- int u, v;
- cin>>u>>v;
- u--, v--;
- tree[u].push_back(v);
- tree[v].push_back(u);
- }
- vector<int> dist(n), prev(n);
- function<void(int, int)> DFS = [&](int u, int p)
- {
- prev[u] = p;
- for(auto v: tree[u])
- {
- if(v == p) continue;
- dist[v] = 1+dist[u];
- DFS(v, u);
- }
- };
- DFS(0, -1);
- int x = max_element(dist.begin(), dist.end()) - dist.begin();
- dist[x] = 0;
- DFS(x, -1);
- int y = max_element(dist.begin(), dist.end()) - dist.begin();
- int r=0, b=0;
- string ans = "";
- for(int i=0; i<n; i++) ans += '.';
- int cnt = dist[y]+1;
- cnt /= 2;
- while(y != -1)
- {
- if(cnt) ans[y] = 'R', r++, cnt--;
- else ans[y] = 'B', b++;
- y = prev[y];
- }
- for(int i=0; i<n; i++)
- {
- if(ans[i] != '.') continue;
- if(r <= b) ans[i] = 'R', r++;
- else ans[i] = 'B', b++;
- }
- cout<<ans<<"\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement