이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (int i = s; i <= e; ++i)
#define rrep(i,s,e) for (int i = s; i >= e; --i)
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define SZ(a) (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
const int mx = 5e5;
vector<vi> leafpads;
vi cur, adj[mx];
int cnt = 0, x;
void dfs (int u, int p) {
if (SZ(adj[u])==1) {
cur.pb(u);
++cnt;
}
for (int v : adj[u]) {
if (v==p) continue;
dfs (v, u);
if (u==x) {
leafpads.pb(cur);
cur.clear();
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
rep (i,1,n-1) {
int u, v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
rep (i,1,n) {
if (SZ(adj[i])>1) {
x = i;
dfs (i,-1);
break;
}
}
cout << (cnt+1)/2 << "\n";
sort(all(leafpads), [&](const vi a, const vi b) {
if (SZ(b)<SZ(a)) return 1;
return 0;
});
int m = SZ(leafpads);
for (int i = 0; i < m; i += 2) {
if (i==m-1 && leafpads[0].empty()) break;
int u = leafpads[i].back();
int v = leafpads[(i+1)%m].back();
cout << u << " " << v << "\n";
leafpads[i].pop_back();
leafpads[(i+1)%m].pop_back();
}
int leafover = -1;
rep (i,0,m-1) {
while (SZ(leafpads[i])>1) {
int e[2];
rep (j,0,1) {
e[j] = leafpads[i].back();
leafpads[i].pop_back();
}
cout << e[0] << " " << e[1] << "\n";
}
if (!leafpads[i].empty()) {
if (leafover==-1) leafover = leafpads[i].back();
else {
cout << leafover << " " << leafpads[i].back() << "\n";
leafover = -1;
}
}
}
if (leafover!=-1) cout << leafover << " " << x << "\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... |