Submission #653417

#TimeUsernameProblemLanguageResultExecution timeMemory
653417pauloamedNetwork (BOI15_net)C++14
100 / 100
653 ms51836 KiB
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 500010;

vector<int> v[MAXN];

vector<int> fol;
void solve(int x, int p){
  bool folha = (v[x].size() == 1);
  for(auto y : v[x]) if(y != p){
    solve(y, x);
  }
  if(folha) fol.push_back(x);
}

int main(){
  int n; cin >> n;
  for(int i = 0; i + 1 < n; ++i){
    int a, b; cin >> a >> b;
    a--; b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }

  solve(0, -1);

  int m = fol.size();
  int mid = (m + 1) / 2;

  cout << mid << "\n";
  for(int i = 0; i < mid; ++i){
    cout << fol[i] + 1 << " " << fol[min(i + mid, m - 1)] + 1 << "\n";
  }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...