Submission #1216173

#TimeUsernameProblemLanguageResultExecution timeMemory
1216173i_love_springNetwork (BOI15_net)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
void solve() {  
  int n;
  cin >> n;
  vector<vector<int>> adj(n + 1);
  vector<int>leaf;
  for (int i = 0; i < n - 1;i++) {
    int u,v;
    cin>> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int r = 1;
  for (int i = 1; i <= n;i++) {
    if (adj[i].size() != 1) {
      r = i;
    }
  }
  function<void(int,int)> dfs = [&](int u,int p) {
    if (adj[u].size() == 1 && adj[u][0] == p) {
      leaf.push_back(u);
    }
    for (int v : adj[u]) {
      if (v != p) dfs(v,u);
    }
  };
  dfs(r,r);
  cout << ((int)leaf.size() + 1)  / 2 << "\n";
  for (int i = 0; i < leaf.size() / 2;i++) {
    cout << leaf[i] << " " << leaf[(int)leaf.size() - i - 1] << "\n";
  }
  if (leaf.size() % 2) cout << r << " " << leaf[leaf.size() / 2] << "\n";
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  //cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...