#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
typedef pair <int, int> pii;
typedef pair <int, bool> pib;
typedef pair <int, pair <int, int> > pip;
typedef pair <pair <int, int>, int> ppi;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define MP make_pair
#define rep(i,a,b) for (long long i=(a);i<(b);i++)
#define rrep(i,a,b) for (long long i=(a);i>(b);i--)
#define SZ(x) ((long long) sizeof(x))
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fileinp freopen("ain.txt","r",stdin);freopen("aout.txt","w",stdout);
const int dx[]={1,-1 ,0,0,1,-1,-1,1};
const int dy[]={0,0,1,-1,-1,-1,1,1};
const int mod=1e9+7;
const int mod2=998244353;
const int INF=(int)1e18;
const int N=100005;
int n,a,b,minans,maxans,cur,ct=1,curval;
int nb[N],minarr[N],maxarr[N],subtree[N];
bool check;
vector<int>adj[N],adj2[N];
vector<pii>temp;
void dfs(int x,int p){
subtree[x]=1;
for(auto it:adj[x]){
if(it!=p){
dfs(it,x);
subtree[x]+=subtree[it];
}
}
}
void dfs2(int x,int p,int chk){
//root tree at centroid
//adj2 is only for layer under centroid and itself
if(chk==-1){
adj2[x].pb(x);
}else{
adj2[chk].pb(x);
}
for(auto it:adj[x]){
if(it!=p){
dfs2(it,x,chk==-1?it:chk);
}
}
}
signed main(){
fastio;
//fileinp;
cin>>n;
rep(i,0,n-1){
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
nb[a]++;nb[b]++;
}
queue<int>q;
rep(i,1,n+1){
minarr[i]=i;
if(nb[i]==1){ //leaf
q.push(i);
}
}
while(!q.empty()){
cur=q.front();
q.pop();
if(minarr[cur]==cur){
curval=-1;
for(auto it:adj[cur]){
if(nb[it]!=0){
curval=it;
break;
}
}
if(curval!=-1){
swap(minarr[cur],minarr[adj[cur][0]]);
}else if(curval==-1){
swap(minarr[cur],minarr[curval]);
}
minans+=2;
}
for(auto it:adj[cur]){
if(nb[it]!=0){
nb[it]--;nb[cur]--;
if(nb[it]<=1){
q.push(it);
}
}
}
}
dfs(1,-1);
ct=1;
rep(i,1,n+1){
if(i>1){
maxans+=2*(min(subtree[i],n-subtree[i]));
}
check=0;
for(auto it:adj[i]){
if(subtree[it]<subtree[i]&&subtree[it]>n/2){
check=1;
}
}
if(n-subtree[i]>n/2){
check=1;
}
if(!check){
ct=i;//centroid
}
}
//cout<<ct<<'\n';
dfs2(ct,-1,-1);
rep(i,1,n+1){
if(adj2[i].size()>0){
temp.pb(MP(adj2[i].size(),i));
}
}
sort(all(temp),greater<pii>());
queue<int>q2;
rep(i,1,temp.size()){ //skip 0 (biggest subtree)
for(auto it:adj2[temp[i].se]){
q2.push(it);
}
}
rep(i,0,temp.size()){
for(auto it:adj2[temp[i].se]){
cur=q2.front();
q2.pop();
maxarr[it]=cur;
//cout<<it<<' '<<cur<<'\n';
q2.push(it);
}
}
cout<<minans<<' '<<maxans<<'\n';
rep(i,1,n+1){
cout<<minarr[i]<<' ';
}
cout<<'\n';
rep(i,1,n+1){
cout<<maxarr[i]<<' ';
}
return 0;
}
Compilation message
Village.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
10 | #pragma GCC optimization ("O3")
|
Village.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
11 | #pragma GCC optimization ("unroll-loops")
|
Village.cpp: In function 'int main()':
Village.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define rep(i,a,b) for (long long i=(a);i<(b);i++)
| ^
Village.cpp:135:5: note: in expansion of macro 'rep'
135 | rep(i,1,temp.size()){ //skip 0 (biggest subtree)
| ^~~
Village.cpp:16:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define rep(i,a,b) for (long long i=(a);i<(b);i++)
| ^
Village.cpp:140:5: note: in expansion of macro 'rep'
140 | rep(i,0,temp.size()){
| ^~~
Village.cpp:94:47: warning: array subscript -1 is below array bounds of 'long long int [100005]' [-Warray-bounds]
94 | swap(minarr[cur],minarr[curval]);
| ~~~~~~~~~~~~~^
Village.cpp:94:47: warning: array subscript -1 is below array bounds of 'long long int [100005]' [-Warray-bounds]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5024 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5076 KB |
Integer parameter [name=vi] equals to 0, violates the range [1, 7] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
3 ms |
5028 KB |
Partially correct |
| 2 |
Partially correct |
3 ms |
5076 KB |
Partially correct |
| 3 |
Partially correct |
3 ms |
5076 KB |
Partially correct |
| 4 |
Partially correct |
4 ms |
5076 KB |
Partially correct |
| 5 |
Partially correct |
3 ms |
5076 KB |
Partially correct |
| 6 |
Partially correct |
3 ms |
5076 KB |
Partially correct |
| 7 |
Incorrect |
3 ms |
5160 KB |
Integer parameter [name=vi] equals to 0, violates the range [1, 1000] |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5024 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
5076 KB |
Integer parameter [name=vi] equals to 0, violates the range [1, 7] |
| 5 |
Halted |
0 ms |
0 KB |
- |
