제출 #656121

#제출 시각아이디문제언어결과실행 시간메모리
656121KahouNetwork (BOI15_net)C++14
63 / 100
6 ms9940 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = 1e5 + 50; int n, sub[N], k, par[N], t; vector<int> adj[N]; vector<int> vc[N]; set<pii> st; vector<pii> out; void dfs(int u, int p) { par[u] = p; for (int v:adj[u]) { if (v == p) continue; dfs(v, u); sub[u] += sub[v]; } } void dfs2(int u, int p) { if (adj[u].size() == 1) { vc[t].push_back(u); } for (int v:adj[u]) { if (v == p) continue; dfs2(v, u); } } void solve() { cin >> n; for (int i = 1; i <= n-1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for (int u = 1; u <= n; u++) { if (adj[u].size() == 1) { k++; sub[u] = 1; } } dfs(1, 0); int r = 0; for (int u = 1; u <= n; u++) { bool flg = 1; for (int v:adj[u]) { if (v == par[u]) flg = flg&&(k-sub[u] <= k/2); else flg = flg&&(sub[v] <= k/2); } if (adj[u].size() > 1 && flg) { r = u; break; } } for (int u:adj[r]) { t++; dfs2(u, r); } for (int i = 1; i <= t; i++) { st.insert({-vc[i].size(), i}); } while (st.size() >= 2) { int A = st.begin()->S; int B = next(st.begin())->S; out.push_back({vc[A].back(), vc[B].back()}); st.erase({-vc[A].size(), A}); st.erase({-vc[B].size(), B}); vc[A].pop_back(); vc[B].pop_back(); if (vc[A].size()) st.insert({-vc[A].size(), A}); if (vc[B].size()) st.insert({-vc[B].size(), B}); } if (st.size()) { int A = st.begin()->S; int u = vc[A].back(); out.push_back({u, r}); st.erase(st.begin()); } cout << out.size() << endl; for (pii x:out) { cout << x.F << ' ' << x.S << endl; } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...