제출 #1216224

#제출 시각아이디문제언어결과실행 시간메모리
1216224i_love_springNetwork (BOI15_net)C++20
0 / 100
12 ms23872 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...