이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define sz(a) a.size()
#define pb(a) push_back(a)
ll N;
vvll g;
ll root;
vpll edges;
vll dp_dfs(ll cur, ll par) {
vll res;
bool is_leaf = true;
for (vll::iterator itr = g[cur].begin(); itr != g[cur].end(); itr++) {
if (*itr == par) continue;
is_leaf = false;
vll child = dp_dfs(*itr, cur);
for (vll::iterator t = child.begin(); t != child.end(); t++) res.pb(*t);
if (sz(res) >= 3) {
ll a = res.back(); res.pop_back();
ll b = res.front(); res.erase(res.begin());
edges.pb(mp(a, b));
}
}
if (is_leaf) {
res.pb(cur);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
g.resize(N);
rep(i, 0, N - 1) {
ll tmpa, tmpb;
cin >> tmpa >> tmpb;
tmpa--; tmpb--;
g[tmpa].pb(tmpb);
g[tmpb].pb(tmpa);
}
root = 0;
while (sz(g[root]) == 1) root++;
vll res = dp_dfs(root, -1);
if (sz(res) == 1) {
edges.pb(mp(res[0], root));
} else {
edges.pb(mp(res[0], res[1]));
}
cout << sz(edges) << "\n";
for (vpll::iterator itr = edges.begin(); itr != edges.end(); itr++) {
cout << itr->first + 1 << " " << itr->second + 1 << "\n";
}
cout << flush;
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... |