SHARE
TWEET

Untitled

a guest Sep 20th, 2016 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define fst first
  4. #define snd second
  5. #define all(x) (x).begin(), (x).end()
  6. #define rall(x) (x).rbegin(), (x).rend()
  7. #define clr(a, v) memset( a , v , sizeof(a) )
  8. #define pb push_back
  9. #define mp make_pair
  10. #define sz size()
  11. #define FORN( i , s , n ) for( int64 i = (s) ; i < (n) ; i++ )
  12. #define FOR( i , n ) FORN( i , 0 , n )
  13. #define FORIT( i , x ) for( typeof x.begin() i = x.begin() ; i != x.end() ; i++ )
  14. #define trace(x)    cout << #x << ": " << x << endl;
  15. #define trace2(x, y) cout << #x << ": " << x << " | " << #y << ": " << y << endl;
  16. #define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  17. #define read ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  18.  
  19. using namespace std;
  20.  
  21. typedef long long int64;
  22. typedef vector <int64> vi;
  23. typedef pair <int64,int64> ii;
  24. typedef vector <string> vs;
  25. typedef vector <ii> vii;
  26.  
  27. int N, L; // size of the tree and number of leaves
  28. vi  adj [100005];
  29.  
  30. int sze [100005]; // number of leaves in the subtree of i
  31. int col [100005]; // color assigned to node i
  32. int maxi[100005]; // maximum number of leaves on a adyacent node of i
  33.  
  34. vii V;
  35.  
  36. void dfs(int v, int parent, int color){
  37.     sze[v] = 0; // assign 0
  38.     col[v] = color;// assign color
  39.     maxi[v] = 0;
  40.  
  41.     FOR(i,adj[v].sz) if ( adj[v][i]!=parent ) {
  42.         dfs(adj[v][i],v,color);
  43.         sze[v]+=sze[adj[v][i]]; //refresh number of leaves
  44.         maxi[v] = max (maxi[v],sze[adj[v][i]]); //refresh maxi
  45.     }
  46.     maxi[v] = max(maxi[v], L-sze[v]); // last refresh for the subtree of the parent
  47.     if (adj[v].sz == 1) {
  48.         sze[v]++; // if v is a leaf add 1
  49.         V.pb(ii(col[v],v+1));
  50.     }
  51. }
  52.  
  53. int main(){
  54.     int a,b;
  55.     while(cin>>N){
  56.         FOR(i,N) adj[i].clear();//clean the graph
  57.         FOR(i,N-1) {
  58.             cin>>a>>b;a--;b--; // made the tree 0-index
  59.             adj[a].pb(b);
  60.             adj[b].pb(a);
  61.         }
  62.         if (N==2) {cout<<"1\n1 2\n"; continue;}//special case
  63.        
  64.         L = 0;
  65.         FOR(i,N) if ( adj[i].sz == 1 ) L++; // number of leaves
  66.                
  67.         // the arrays sze, col and maxi are not cleared because are assigned in each step
  68.         dfs(0,-1,0);// to find the centroid
  69.                
  70.         int root = -1;
  71.         FOR(i,N) if (adj[i].sz>1 and maxi[i]<=(L/2) ) root = i; // find the centroid
  72.        
  73.         int  color = 0;    
  74.        
  75.         // assign the color to each  neighbord of the root
  76.         V.clear();
  77.         FOR(i,adj[root].sz) dfs( adj[root][i], root, color++ );
  78.  
  79.         sort(all(V));
  80.          // vector of leaves    
  81.         /*FOR(i,N) if ( adj[i].sz == 1 ) V.pb( ii(col[i],i+1) );
  82.         sort(all(V));// sort by color by special cmp
  83.        */
  84.         // if L%2==1 add the first node
  85.         if (V.sz%2 == 1) V.pb( V[0] );
  86.        
  87.         cout<<V.sz/2<<endl;
  88.         FOR(i, V.sz/2) cout<< V[i].snd <<" "<<V[i+(V.sz/2)].snd<<endl;
  89.        
  90.     }
  91. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top