이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;
vector<vector<int>> g;
vector<int> leaves;
int n;
void preprocess(int u, int p = -1) {
leaves[u] = 0;
if((int)g[u].size() == 1) ++leaves[u];
for(int v : g[u]) {
if(v == p) continue;
preprocess(v, u);
leaves[u] += leaves[v];
}
}
int dfs(int u, int p = -1) {
int max_leaves = 0;
if(p != -1) max_leaves = leaves[0] - leaves[u];
for(int v : g[u]) {
if(v == p) continue;
max_leaves = max(max_leaves, leaves[v]);
}
if(max_leaves <= leaves[0] / 2) return u;
for(int v : g[u]) {
if(v == p) continue;
int w = dfs(v, u);
if(w != -1) return w;
}
return -1;
}
void solve() {
cin >> n;
g.resize(n);
leaves.resize(n);
for(int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
preprocess(0);
int v = dfs(0);
vector<vector<int>> F;
vector<int> P;
function<void(vector<int>&, int, int)> get = [&](vector<int>& f, int u, int p) {
if(g[u].size() == 1) f.push_back(u);
else {
for(int v : g[u]) {
if(v == p) continue;
get(f, v, u);
}
}
};
for(int u : g[v]) {
F.push_back({});
get(F.back(), u, v);
}
P.resize(F.size());
iota(P.begin(), P.end(), 0);
sort(P.begin(), P.end(), [&F](int e, int d) {
return F[e].size() < F[d].size();
});
vector<ii> pairs;
int lo = 0, hi = (int)F.size() - 1;
while(lo < hi) {
int u = F[P[lo]].back();
int v = F[P[hi]].back();
pairs.emplace_back(u + 1, v + 1);
F[P[lo]].pop_back();
F[P[hi]].pop_back();
if(F[P[lo]].empty()) ++lo;
if(F[P[hi]].empty()) --hi;
}
for(auto& x : F) {
if(x.empty()) continue;
int u = x.back();
sort(g[u].begin(), g[u].end());
if(g[u][0]) pairs.emplace_back(u + 1, 1);
else if(g[u].back() < n - 1) pairs.emplace_back(u + 1, n);
else {
for(int i = 1; i < (int)g[u].size(); ++i) {
if(g[u][i] - g[u][i - 1] > 1) {
pairs.emplace_back(u + 1, g[u][i - 1] + 1);
break;
}
}
}
break;
}
cout << pairs.size() << '\n';
for(auto [u, v] : pairs) cout << u << ' ' << v << '\n';
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |