Advertisement
Ankit_132

D

Mar 20th, 2024
607
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     int t;
  6.     cin>>t;
  7.    
  8.     while(t--){
  9.         int n;
  10.         cin>>n;
  11.        
  12.         vector<vector<int>> tree(n);
  13.        
  14.         for(int i=0; i<n-1; i++)
  15.         {
  16.             int u, v;
  17.             cin>>u>>v;
  18.            
  19.             u--, v--;
  20.            
  21.             tree[u].push_back(v);
  22.             tree[v].push_back(u);
  23.         }
  24.        
  25.         vector<int> dist(n), prev(n);
  26.        
  27.         function<void(int, int)> DFS = [&](int u, int p)
  28.         {
  29.             prev[u] = p;
  30.             for(auto v: tree[u])
  31.             {
  32.                 if(v == p)      continue;
  33.                 dist[v] = 1+dist[u];
  34.                 DFS(v, u);
  35.             }
  36.         };
  37.        
  38.        
  39.         DFS(0, -1);
  40.        
  41.         int x = max_element(dist.begin(), dist.end()) - dist.begin();
  42.        
  43.         dist[x] = 0;
  44.        
  45.         DFS(x, -1);
  46.        
  47.         int y = max_element(dist.begin(), dist.end()) - dist.begin();
  48.        
  49.         int r=0, b=0;
  50.        
  51.         string ans = "";
  52.         for(int i=0; i<n; i++)      ans += '.';
  53.        
  54.         int cnt = dist[y]+1;
  55.         cnt /= 2;
  56.        
  57.         while(y != -1)
  58.         {
  59.             if(cnt)         ans[y] = 'R', r++, cnt--;
  60.             else            ans[y] = 'B', b++;
  61.            
  62.             y = prev[y];
  63.         }
  64.        
  65.         for(int i=0; i<n; i++)
  66.         {
  67.             if(ans[i] != '.')       continue;
  68.            
  69.             if(r <= b)      ans[i] = 'R', r++;
  70.             else            ans[i] = 'B', b++;
  71.         }
  72.        
  73.         cout<<ans<<"\n";
  74.     }
  75. }
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement