#include <bits/stdc++.h>
using namespace std;
#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define ff first
#define ss second
#define pii pair<int,int>
#define pb push_back
vector<vector<int>> graph;
vector<int> sz,order,depth,ansmx,ansmn,first,second;
int n,ctrd,fre,sum;
void dfs(int u,int p){
order.pb(u);
for(int v:graph[u]){
if(v==p) continue;
if(second[u]==-1 and first[u]!=-1){
second[u]=v;
}
if(first[u]==-1){
first[u]=v;
}
depth[v]=depth[u]+1;
dfs(v,u);
sz[u]+=sz[v];
}
}
int centroid(int u, int p){
for(int v:graph[u]){
if(v==p) continue;
if(sz[v]*2>n){
return centroid(v,u);
}
}
return u;
}
void mindfs(int u,int p){
for(int v:graph[u]){
if(v==p) continue;
mindfs(v,u);
}
if(ansmn[u]!=0) return;
if(graph[p].size()%2==0){
if(ansmn[p]==0){
ansmn[p]=u;
ansmn[u]=p;
sum+=2;
}else{
if(fre==0){
fre=u;
}else{
ansmn[u]=fre;
ansmn[fre]=u;
sum+=4;
}
}
}else{
if(ansmn[p]==0){
if(u==first[p]){
ansmn[p]=second[p];
ansmn[u]=p;
ansmn[second[p]]=u;
sum+=4;
}
}else{
if(fre==0){
fre=u;
}else{
ansmn[u]=fre;
ansmn[fre]=u;
sum+=4;
}
}
}
}
int32_t main(){
speedIO;
int t,m,q;
//cin>>t;
t=1;
while(t--){
//string s;
cin>>n;
graph.clear();
graph.resize(n+1);
sz.clear();
sz.resize(n+1,1);
order.clear();
depth.clear();
depth.resize(n+1,0);
ansmx.clear();
ansmx.resize(n+1);
ansmn.clear();
ansmn.resize(n+1,0);
first.clear();
first.resize(n+1,-1);
second.clear();
second.resize(n+1,-1);
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
graph[u].pb(v);
graph[v].pb(u);
}
dfs(1,0);
ctrd=centroid(1,0);
depth.clear();
depth.resize(n+1,0);
order.clear();
graph[ctrd].pb(0);
graph[0].pb(ctrd);
first.clear();
first.resize(n+1,-1);
second.clear();
second.resize(n+1,-1);
dfs(ctrd,0);
int mx=0,mn;
for(int i=1;i<=n;i++){
mx+=depth[i];
ansmx[order[i-1]]=order[(i+n/2)%n];
}
mx*=2;
mindfs(0,-1);
if(ansmn[ctrd]==0){
int x=first[ctrd];
if(ansmn[ansmn[x]]==x){
ansmn[ctrd]=ansmn[x];
ansmn[x]=ctrd;
sum+=2;
}else{
ansmn[ansmn[x]]=ctrd;
ansmn[ctrd]=ansmn[x];
ansmn[x]=ctrd;
}
}
cout<<mx<<' '<<sum<<'\n';
for(int i=1;i<=n;i++){
cout<<ansmx[i]<<' ';
}
cout<<'\n';
for(int i=1;i<=n;i++){
cout<<ansmn[i]<<' ';
}
cout<<'\n';
}
//}
return 0;
}
Compilation message
Village.cpp: In function 'int32_t main()':
Village.cpp:132:12: warning: unused variable 'mn' [-Wunused-variable]
132 | int mx=0,mn;
| ^~
Village.cpp:89:8: warning: unused variable 'm' [-Wunused-variable]
89 | int t,m,q;
| ^
Village.cpp:89:10: warning: unused variable 'q' [-Wunused-variable]
89 | int t,m,q;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Integer parameter [name=vi] equals to 0, violates the range [1, 4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Integer parameter [name=vi] equals to 0, violates the range [1, 256] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Integer parameter [name=vi] equals to 0, violates the range [1, 4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
