#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> adj[100005];
ll posmin[100005], posmax[100005], sz[100005], dec1[100005], dec2[100005], ansmin = 0, ansmax = 0, n, cnt = 0;
vector<bool> vis;
void dfs(int u, int p){
sz[u] = 1;
for(auto v : adj[u]){
if(v == p)continue;
dfs(v, u);
sz[u] += sz[v];
if(vis[v]) continue;
vis[u] = true;
swap(posmin[u], posmin[v]);
ansmin += 2;
}
if(u) ansmax += min(sz[u], n - sz[u]) * 2;
else if(!vis[0]){
swap(posmin[0], posmin[adj[0][0]]);
ansmin += 2;
}
}
void findroot(int u, int p){
for(auto v : adj[u]){
if(v == p) continue;
if(sz[v] > (n >> 1)){
dec1[v] = 0;
dec2[0] = v;
findroot(v, u);
}
}
}
void encode(int u, int p){
dec1[cnt] = u;
dec2[u] = cnt++;
for(auto v : adj[u]){
if(v == p) continue;
encode(v, u);
}
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n;
iota(posmin, posmin + n, 0);
iota(posmax, posmax + n, 0);
for(int i = 0; i < n - 1; i++){
int u, v; cin >> u >> v;
adj[u - 1].push_back(v - 1);
adj[v - 1].push_back(u - 1);
}
dfs(0, 0);
findroot(0, 0);
encode(dec1[0], dec1[0]);
for(int i = 0; i < n; i++) posmax[i] = dec1[(dec2[i] + n / 2)%n];
cout << ansmin << ' ' << ansmax << '\n';
for(auto x : posmin) cout << x + 1 << ' ';
cout << '\n';
for(auto x : posmax) cout << x + 1 << ' ';
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
12892 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
12892 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
12892 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
