Submission #1216157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216157		i_love_spring	Network (BOI15_net)	C++20	0 / 100	2095 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,leaves;
  int cnt1= 0;
  for (int i = 0; i < cnt;i++) {
    if (leaf[id[i]].empty()) continue;
    while (!leaf[id[i]].empty() && (ans % 2 != 1 || cnt1 != cnt - 1 || leaf[id[i]].size() != 1)) {
    //  cerr << id[i] << " " << leaf[id[i]].size() << "\n"; 
      for (int j = i + 1; j < cnt && (!leaf[id[i]].empty() && (ans % 2 != 1 || cnt1 != cnt - 1 || leaf[id[i]].size() != 1));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)});
        leaves.insert({u,i});
        leaves.insert({v,j});
        leaf[id[i]].pop_back();
        leaf[id[j]].pop_back();
        if (leaf[id[i]].empty()) cnt1++;
        if (leaf[id[j]].empty()) cnt1++;
      }
    }
  }
  if (ans % 2) {
    int u = 0,t1 = 0;
    for (int i = 0; i < cnt;i++) {
      if (leaf[id[i]].size()) {
        u = leaf[id[i]][0];
        t1 = i;
        break;
      }
    } 
    for (auto [v,t] : leaves) {
      if (t != t1) {
        st.insert({u,v});
        break;
      }
    }
  }
  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