Submission #653417

#	Time	Username	Problem	Language	Result	Execution time	Memory
653417		pauloamed	Network (BOI15_net)	C++14	100 / 100	653 ms	51836 KiB

net

#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";
  }

}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37