이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using pii = pair<int, int>;
const int N = 5e5 + 5;
vector<int> g[N], lvs[N];
bool matched[N];
vector<pii> ant;
int n, root;
static void dfs(int u) {
if (g[u].empty())
lvs[u].push_back(u);
int total = 0;
for (auto v: g[u]) {
g[v].erase(remove(begin(g[v]), end(g[v]), u), end(g[v]));
dfs(v);
total+= lvs[v].size(); }
sort(begin(g[u]), end(g[u]), [&](const int &a, const int &b) {
return lvs[a].size() > lvs[b].size(); });
if (g[u].size() == 1)
swap(lvs[g[u][0]], lvs[u]);
for (auto v: g[u]) {
while (lvs[u].size() && lvs[v].size() && total > (u == root ? 0 : 2)) {
ant.emplace_back(lvs[u].back(), lvs[v].back());
lvs[u].pop_back();
lvs[v].pop_back();
total-= 2; }
while (lvs[v].size()) {
lvs[u].push_back(lvs[v].back());
lvs[v].pop_back(); } } }
int main() {
#ifdef HOME
freopen("network.in", "r", stdin);
freopen("network.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int u, v, i = 1; i < n; ++i) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u); }
for (root = 1; g[root].size() == 1; ++root);
dfs(root);
if (lvs[root].size())
ant.emplace_back(root, lvs[root][0]);
cout << ant.size() << '\n';
for (auto i: ant)
cout << i.x << ' ' << i.y << '\n';
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... |