#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> > graph;
vector<int> match,prem;
vector<vector<int> > dp;
vector<int> sz,ord;
int n;
typedef long long ll;
ll max_cnt=0;
void dfs_min(int node,int parent){
sz[node]++;
for(auto x:graph[node]){
if(x==parent) continue;
dfs_min(x,node);
sz[node]+=sz[x];
dp[node][0]+=max(dp[x][0],dp[x][1]);
}
for(auto x:graph[node]){
if(x==parent) continue;
if(dp[node][1]<dp[node][0]-max(dp[x][0],dp[x][1])+dp[x][0]+1){
dp[node][1]=dp[node][0]-max(dp[x][0],dp[x][1])+dp[x][0]+1;
prem[node]=x;
}
}
}
void dfs_match(int node,int parent,bool flag){
if(flag||dp[node][0]>=dp[node][1]){
for(auto x:graph[node]){
if(x==parent) continue;
dfs_match(x,node,0);
}
}
else{
match[node]=prem[node];
match[prem[node]]=node;
for(auto x:graph[node]){
if(x==parent) continue;
if(x==prem[node]) dfs_match(x,node,1);
else dfs_match(x,node,0);
}
}
}
int dfs_cent(int node,int parent){
for(auto x:graph[node]){
if(x==parent) continue;
if(sz[x]>n/2) return dfs_cent(x,node);
}
return node;
}
void dfs_sz(int node,int parent){
sz[node]=1;
for(auto x:graph[node]){
if(x==parent) continue;
dfs_sz(x,node);
sz[node]+=sz[x];
}
if(parent!=0) max_cnt+=2*min(1ll*sz[node],1ll*(n-sz[node]));
}
void dfs_ord(int node,int parent){
if(parent!=0) ord.push_back(node);
for(auto x:graph[node]){
if(x==parent) continue;
dfs_ord(x,node);
}
}
int main(){
cin>>n;
graph.resize(n+1);
prem.resize(n+1);
sz.resize(n+1);
int a,b;
for(int i=1;i<n;i++){
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dp.resize(n+1,vector<int>(2));
match.resize(n+1,-1);
dfs_min(1,0);
dfs_match(1,0,0);
vector<int> ans_min(n+1);
for(int i=1;i<=n;i++){
if(match[i]!=-1){
ans_min[i]=match[i];
}
else ans_min[i]=i;
}
int min_cnt=max(dp[1][1],dp[1][0])*2;
for(int i=1;i<=n;i++){
if(match[i]==-1){
swap(ans_min[i],ans_min[graph[i][0]]),min_cnt+=2;
}
}
int cent=dfs_cent(1,0);
dfs_sz(cent,0);
sort(graph[cent].begin(),graph[cent].end(),[&](int a,int b){return sz[a]>sz[b];});
dfs_ord(cent,0);
vector<int> ans_max(n+1);
for(int i=1;i<=n;i++) ans_max[i]=i;
if(n&1){
for(int i=0;i<n/2;i++) swap(ans_max[ord[i]],ans_max[ord[i+n/2]]);
swap(ans_max[cent],ans_max[1]);
}
else{
ord.push_back(cent);
for(int i=0;i<n/2;i++) swap(ans_max[ord[i]],ans_max[ord[i+n/2]]);
}
cout<<min_cnt<<" "<<max_cnt<<"\n";
for(int i=1;i<=n;i++) cout<<ans_min[i]<<" \n"[i==n];
for(int i=1;i<=n;i++) cout<<ans_max[i]<<" \n"[i==n];
}
Compilation message
Village.cpp: In function 'int main()':
Village.cpp:97:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
97 | sort(graph[cent].begin(),graph[cent].end(),[&](int a,int b){return sz[a]>sz[b];});
| ^~~~
| qsort
