IOICJ 92 Double path tree ( Ad hoc, Timestamp )

Problem Description:
Given a tree, you want to do the least amount of operations to assert that for any two distinct nodes, there are at least two distinct simple paths that connect them.

Constraints:
1≤T≤300
3≤n≤1e5
1≤xi,yi≤n
A valid tree is given
Input file is less than 10 MB

Sample Input:
2
3
1 2
2 3
5
1 2
1 3
2 4
2 5

Sample Output:
1
1 3
2
4 5
4 3

Solution:
Consider extending the tree out so that no edges intersect. Imagine that all the leaves form somewhat a circle. Join every leaf with the leaf that is half the number of leaves away clockwise.

const int MAXN = ( int ) 1e5;

int N;
vvi G;
int ROOT;

void init(){
  cin >> N;
  G = vvi( N );
  for( int i = 0; i < N - 1; ++i ){
    int u, v; cin >> u >> v; --u, --v;
    G[ u ].emplace_back( v );
    G[ v ].emplace_back( u );
  }
  for( int i = 0; i < N; ++i ){
    if( G[ i ].size() > 1 ){
      ROOT = i;
      break;
    }
  }
}

int TS;
int tin[ MAXN ];

void build_ts( int u, int fa ){
  tin[ u ] = ++TS;
  for( int v : G[ u ] ){
    if( v == fa ) continue;
    build_ts( v, u );
  }
}

void preprocess(){
  TS = 0;
  build_ts( ROOT, -1 );
}

bool cmp( int a, int b ){
  return tin[ a ] < tin[ b ];
}

void solve(){
  vi leaf;
  for( int i = 0; i < N; ++i ){
    if( G[ i ].size() > 1 ) continue;
    leaf.emplace_back( i );
  }
  sort( leaf.begin(), leaf.end(), cmp );
  cout << ( leaf.size() + 1 ) / 2 << endl;
  for( int i = 0; i < leaf.size() / 2; ++i ){
    cout << leaf[ i ] + 1 << " " << leaf[ leaf.size() / 2 + i ] + 1 << endl;
  }
  if( leaf.size() & 1 ){
    cout << leaf.back() + 1 << " " << leaf[ leaf.size() / 2 ] + 1 << endl;
  }
}