#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 10;
const long long MAX = 1'000'000'000'000'000'000;
int n;
vector<int> ad[N];
namespace findMin {
long long f[N][2];
vector<tuple<int, int, int>> trace[N][2];
void dfs0(int u, int p = -1) {
f[u][1] = 0;
vector<int> best;
for (const auto& v : ad[u]) {
if (v == p) continue;
dfs0(v, u);
best.push_back(v);
}
if (best.size()) {
sort(best.begin(), best.end(), [&](const auto& a, const auto& b) {
return f[a][1] - f[a][0] > f[b][1] - f[b][0];
});
{ //f[u][1]
vector<int> vt = best;
auto& ret = f[u][1];
auto& tr = trace[u][1];
while (vt.size() > 1) {
long long value = min(MAX, f[vt.back()][1] + f[vt.end()[-2]][1] + 4);
if (value <= min(MAX, f[vt.back()][0] + f[vt.end()[-2]][0])) {
ret = min(MAX, ret + value);
tr.emplace_back(0, vt.back(), vt.end()[-2]);
vt.pop_back();
vt.pop_back();
} else break;
}
for (const auto& x : vt) {
ret = min(MAX, ret + f[x][0]);
tr.emplace_back(1, x, 0);
}
}
{ //f[u][0]
vector<int> vt = best;
auto& ret = f[u][0];
auto& tr = trace[u][0];
ret = f[vt.back()][1] + 2;
tr.emplace_back(2, vt.back(), 1);
vt.pop_back();
for (const auto& x : vt) {
if (f[x][1] + 2 <= f[x][0]) {
ret = min(MAX, ret + f[x][1] + 2);
tr.emplace_back(2, x, 1);
} else {
ret = min(MAX, ret + f[x][0]);
tr.emplace_back(2, x, 0);
}
}
}
if (f[u][0] > f[u][1] + 2) {
f[u][0] = min(MAX, f[u][1] + 2);
trace[u][0] = {make_tuple(3, best.back(), 0)};
}
}
if (f[u][1] >= MAX || f[u][1] < 0) f[u][1] = 2 * MAX;
if (f[u][0] >= MAX || f[u][0] < 0) f[u][0] = MAX;
}
int vt[N];
void dfs1(int u, int st) {
for (const auto& [type, a, b] : trace[u][st]) {
if (!type) {
dfs1(a, 1); dfs1(b, 1);
swap(vt[a], vt[b]);
} else if (type == 1) {
dfs1(a, 0);
} else if (type == 2) {
dfs1(a, b);
if (b) swap(vt[u], vt[a]);
} else {
dfs1(u, 1);
swap(vt[u], vt[a]);
}
}
}
int length;
vector<int> answer;
void solve() {
memset(f, 14, sizeof f);
dfs0(1);
iota(vt + 1, vt + n + 1, 1);
dfs1(1, 0);
length = f[1][0];
answer = vector<int>(vt + 1, vt + n + 1);
}
}
namespace findMax {
long long length;
int d[N], sz[N];
int st[N], ed[N], rvs[N], it;
int f[N][17], lg[N];
void dfs0(int u, int p = -1) {
sz[u] = 1;
st[u] = ++it; rvs[it] = u;
for (const auto& v : ad[u]) {
if (v == p) continue;
d[v] = d[u] + 1;
dfs0(v, u);
ed[u] = ++it; rvs[it] = u;
sz[u] += sz[v];
length += 2 * min(sz[v], n - sz[v]);
}
}
void init() {
for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= it; ++i) f[i][0] = rvs[i];
for (int j = 1; j <= 16; ++j) {
for (int i = 1; i + (1 << j) - 1 <= it; ++i) {
auto lt = f[i][j - 1], rt = f[i + (1 << j - 1)][j - 1];
// if (i == st[5]) cerr << j << " " << i + (1 << j - 1) + (1 << j - 1) - 1 << "\n";
f[i][j] = (d[lt] <= d[rt] ? lt : rt);
}
}
}
int lca(int u, int v) {
int l = min(st[u], st[v]), r = max(st[u], st[v]);
int j = lg[r - l + 1];
auto lt = f[l][j], rt = f[r - (1 << j) + 1][j];
return d[lt] <= d[rt] ? lt : rt;
}
int dis(int u, int v) { return d[u] + d[v] - 2 * d[lca(u, v)]; }
vector<int> answer;
void solve() {
dfs0(1);
init();
answer.resize(n); iota(answer.begin(), answer.end(), 1);
for (;;) {
long long ret = 0;
random_shuffle(answer.begin(), answer.end());
for (int i = 1; i <= n; ++i) {
if (answer[i - 1] == i) { ret = 0; break; }
ret += dis(i, answer[i - 1]);
}
if (ret == length) break;
}
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
ad[u].push_back(v);
ad[v].push_back(u);
}
findMin::solve();
findMax::solve();
cout << findMin::length << " " << findMax::length << "\n";
for (int i = 0; i < n; ++i) cout << findMin::answer[i] << " \n"[i == n - 1];
for (int i = 0; i < n; ++i) cout << findMax::answer[i] << " \n"[i == n - 1];
}
Compilation message
Village.cpp: In function 'void findMax::init()':
Village.cpp:128:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
128 | auto lt = f[i][j - 1], rt = f[i + (1 << j - 1)][j - 1];
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12136 KB |
Output is correct |
| 7 |
Correct |
2 ms |
12140 KB |
Output is correct |
| 8 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
1 ms |
12124 KB |
Output is correct |
| 11 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 12 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 13 |
Correct |
2 ms |
12136 KB |
Output is correct |
| 14 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 15 |
Correct |
20 ms |
12156 KB |
Output is correct |
| 16 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 17 |
Execution timed out |
1099 ms |
12124 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
12124 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12136 KB |
Output is correct |
| 7 |
Correct |
2 ms |
12140 KB |
Output is correct |
| 8 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
1 ms |
12124 KB |
Output is correct |
| 11 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 12 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 13 |
Correct |
2 ms |
12136 KB |
Output is correct |
| 14 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 15 |
Correct |
20 ms |
12156 KB |
Output is correct |
| 16 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 17 |
Execution timed out |
1099 ms |
12124 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
