#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll M = 307;
const ll LG = 31;
ll n, m, k;
vector<int>g[N];
vector<int>res_mn, res_mx;
ll ans_mn = 0, ans_mx = 0;
bool used[N];
int sz[N];
stack<int>st[N];
bool useds[N];
bool comp(int x, int y) {
return st[x].size() < st[y].size();
}
multiset<int, decltype(&comp)> s(&comp);
void dfs(int v, int par = -1) {
for (int to : g[v]) {
if (to != par) {
dfs(to, v);
}
}
vector<int>leaves;
for (int to : g[v]) {
if (to != par) {
if (!used[to]) {
leaves.push_back(to);
}
}
}
if (leaves.size() != 0) {
ans_mn += leaves.size() * 2;
res_mn[v] = leaves[0];
for (int i = 0; i < leaves.size() - 1; i++) {
res_mn[leaves[i]] = leaves[i + 1];
}
res_mn[leaves[leaves.size() - 1]] = v;
for (int to : leaves) {
used[to] = true;
}
used[v] = true;
}
}
void calc_sz(int v, int par = -1) {
sz[v] = 1;
for (int to : g[v]) {
if (to != par) {
calc_sz(to, v);
sz[v] += sz[to];
}
}
if (par != -1) {
ans_mx += 2 * min(ll(sz[v]), n - sz[v]);
}
}
int centroid(int v, int par = -1) {
for (int to : g[v]) {
if (to != par) {
if (sz[to] > n / 2) {
return centroid(to, v);
}
}
}
return v;
}
void inch_tenum_es_qci_stacki_mej(int v, int par, int cur) {
if (!useds[v])st[cur].push(v);
for (int to : g[v]) {
if (to != par) {
inch_tenum_es_qci_stacki_mej(to, v, cur);
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
int leaf = 0;
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int v = 1; v <= n; v++) {
if (g[v].size() == 1) {
leaf = v;
break;
}
}
int root = g[leaf][0];
res_mn.resize(n + 1, 0);
res_mx.resize(n + 1, 0);
dfs(root);
calc_sz(1);
int c = centroid(1);
if (n % 2 != 0) {
res_mx[c] = g[c][0];
res_mx[g[c][0]] = g[c][1];
res_mx[g[c][1]] = c;
useds[c] = useds[g[c][0]] = useds[g[c][1]] = true;
}
int cur_stack = 0;
for (int to : g[c]) {
inch_tenum_es_qci_stacki_mej(to, c, cur_stack++);
}
int minim = 0;
for (int i = 0; i < cur_stack; i++) {
if (comp(i, minim)) {
minim = i;
}
//cout << i << ": " << st[i].size() << endl;
}
if (!useds[c])st[minim].push(c);
for (int i = 0; i < cur_stack; i++) {
if(st[i].size()!=0)s.insert(i);
}
while (!s.empty()) {
//cout << s.size() << endl;
int bg = *s.rbegin();
s.erase(--s.end());
int sbg = *s.rbegin();
s.erase(--s.end());
int v1 = st[bg].top();
int v2 = st[sbg].top();
res_mx[v1] = v2;
res_mx[v2] = v1;
st[bg].pop();
st[sbg].pop();
if (st[bg].size() != 0) {
s.insert(bg);
}
if (st[sbg].size() != 0) {
s.insert(sbg);
}
//cout << bg << " " << sbg << endl;
}
cout << ans_mn << " " << ans_mx << endl;
for (int v = 1; v <= n; v++) {
cout << res_mn[v] << " ";
}
cout << endl;
for (int v = 1; v <= n; v++) {
cout << res_mx[v] << " ";
}
cout << endl;
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
Compilation message
Village.cpp: In function 'void dfs(int, int)':
Village.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < leaves.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
139592 KB |
Output is correct |
| 2 |
Correct |
81 ms |
139632 KB |
Output is correct |
| 3 |
Runtime error |
192 ms |
262144 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
139604 KB |
Output is correct |
| 2 |
Correct |
80 ms |
139672 KB |
Output is correct |
| 3 |
Correct |
79 ms |
139600 KB |
Output is correct |
| 4 |
Correct |
86 ms |
139596 KB |
Output is correct |
| 5 |
Correct |
84 ms |
139688 KB |
Output is correct |
| 6 |
Correct |
81 ms |
139636 KB |
Output is correct |
| 7 |
Correct |
83 ms |
139724 KB |
Output is correct |
| 8 |
Correct |
87 ms |
139724 KB |
Output is correct |
| 9 |
Correct |
83 ms |
139612 KB |
Output is correct |
| 10 |
Correct |
80 ms |
139720 KB |
Output is correct |
| 11 |
Correct |
81 ms |
139688 KB |
Output is correct |
| 12 |
Correct |
80 ms |
139660 KB |
Output is correct |
| 13 |
Runtime error |
208 ms |
262144 KB |
Execution killed with signal 11 |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
139592 KB |
Output is correct |
| 2 |
Correct |
81 ms |
139632 KB |
Output is correct |
| 3 |
Runtime error |
192 ms |
262144 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
