Submission #1216224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216224		i_love_spring	Network (BOI15_net)	C++20	0 / 100	12 ms	23872 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int N = 500005;
vector<int> g[N],leaf[N];
int par[N],n;
int find(int u) {
  int v = u;
  while (par[u] != u) u = par[u];
  while (v != u) {
    int tmp = par[v];
    par[v] = u;
    v = tmp;
  }
  return u;
}
void unite(int u,int v) {
  u = find(u);
  v = find(v);
  if (u == v) return;
  while ((leaf[u].size() > 1 || leaf[v].size() > 1) && leaf[u].size() && leaf[v].size()) {
    cout << leaf[u].back() << " " << leaf[v].back() << "\n";
    leaf[u].pop_back();
    leaf[v].pop_back();
  }
  par[v] = u;
  while (leaf[v].size()) {
    leaf[u].push_back(leaf[v].back());
    leaf[v].pop_back();
  }
}
void dfs(int u,int p) {
  for (int v : g[u]) {
    if (v == p) continue;
    dfs(v,u);
    unite(u,v);
  }
}
void solve() {  
  cin >> n;
  for (int i = 0; i < n - 1;i++) {
    int u,v;
    cin>> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int r = 1,ans = 0;
  for (int i = 1; i <= n;i++) {
    par[i] = i;
    if (g[i].size() != 1) {
      r = i;
    }
    if (g[i].size() == 1) {
      ans++;
      leaf[i].push_back(i);
    }
  }
  cout << (ans + 1) / 2 << "\n";
  dfs(r,0);
  int v = find(r);
  if (leaf[v].size() % 2) leaf[v].push_back(r);
  for (int i = 0; i < leaf[v].size() / 2;i++) cout << leaf[v][i] <<" " << leaf[v][n - i - 1] << "\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