This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<vector<int>> v(n + 1);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
vector<int> dp(n + 1);
function<void(int, int)> dfs = [&](int x, int p) {
if ((int)v[x].size() == 1) {
dp[x] += 1;
}
for (auto z : v[x]) {
if (z == p) continue;
dfs(z, x);
dp[x] += dp[z];
}
};
int tot;
for (int i = 1; i <= n; i++) {
if ((int)v[i].size() > 1) {
dfs(i, i);
tot = dp[i];
break;
}
}
int mn = n + 1, rt = -1;
for (int i = 1; i <= n; i++) {
if (dp[i] >= tot / 2) {
if (dp[i] < mn) {
mn = dp[i];
rt = i;
}
}
}
vector<int> leafs;
function<void(int, int)> dfs2 = [&](int x, int p) {
if ((int)v[x].size() == 1) {
leafs.push_back(x);
}
for (auto z : v[x]) {
if (z == p) continue;
dfs2(z, x);
}
};
dfs2(rt, rt);
if ((int)leafs.size() % 2 == 1) {
leafs.push_back(leafs.back());
}
cout << (int)leafs.size() / 2 << '\n';
for (int i = 0; i < (int)leafs.size() / 2; i++) cout << leafs[i] << " " << leafs[i + (int)leafs.size() / 2] << '\n';
return 0;
}
Compilation message (stderr)
net.cpp: In function 'int32_t main()':
net.cpp:52:34: warning: 'tot' may be used uninitialized in this function [-Wmaybe-uninitialized]
52 | if (dp[i] >= tot / 2) {
| ~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |