Submission #1216163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216163		i_love_spring	Network (BOI15_net)	C++20	0 / 100	2096 ms	324 KiB

net

#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<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,mn = n;
  for (int i = 1; i <= n;i++) {
    if (adj[i].size() != 1) {
      if (adj[i].size() < mn) {
        mn = adj[i].size();
        r = i;
      }
    }
  }
  int cnt = 0;
  leaf.resize((int)adj[r].size() + 5);
  function<void(int,int)> dfs = [&](int u,int p) {
    if (adj[u].size() == 1 && adj[u][0] == p) {
      leaf[cnt].push_back(u);
    }
    for (int v : adj[u]) {
      if (v != p) dfs(v,u);
    }
  };
  int ans = 0;
  for (int u : adj[r]) {
    dfs(u,r);
    ans += (int)leaf[cnt++].size();
  }
  vector<int>id(cnt);
  iota(id.begin(),id.end(),0);
  sort(id.begin(),id.end(),[&](int i,int j){
    return (int)leaf[i].size() > (int)leaf[j].size();
  });
  // for (int x : id) cerr <<  x << " ";
  // cerr << "\n";
  cout << (ans + 1) / 2 << "\n";
  set<ar<int,2>> st;
  int cnt1= 0,add = -1;
  if (ans % 2) {
    for (int i = 0; i < cnt;i++) {
      if ((int)leaf[id[i]].size() % 2 == 1) {
        add = leaf[id[i]].back();
        leaf[id[i]].pop_back();
        if (leaf[id[i]].empty())cnt1++;
        break;
      }
    }
    st.insert({r,add});
  }
  for (int i = 0; i < cnt;i++) {
    if (leaf[id[i]].empty()) continue;
    while (!leaf[id[i]].empty()) {
      for (int j = i + 1; j < cnt && !leaf[id[i]].empty();j++) {
        if (leaf[id[j]].empty()) continue;
        int u = leaf[id[i]].back();
        int v = leaf[id[j]].back();
        st.insert({min(u,v),max(u,v)});
        leaf[id[i]].pop_back();
        leaf[id[j]].pop_back();
        if (leaf[id[i]].empty()) cnt1++;
        if (leaf[id[j]].empty()) cnt1++;
      }
    }
  }
  for (auto [u,v] : st) cout << u << " " << v << "\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;
} 

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