//AE86!!!!
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
int n,u,v,cnt=1,h1[N],h2[N],sz[N],seq[N],lv[N],P[20][N];
ll ans1,ans2;
vector<int> adj[N];
void A1(int u,int p){
for(auto v : adj[u]){
if(v == p) continue;
A1(v,u);
}
if(h1[u] == u){
if(u == 1) swap(h1[u],h1[adj[1][0]]);
else swap(h1[u],h1[p]);
ans1 += 2;
}
}
int size(int u,int p){
sz[u] = 1;
for(auto v : adj[u]) if(v != p) sz[u] += size(v,u);
return sz[u];
}
int find_cen(int u,int p,int all){
for(auto v : adj[u]) if(v != p && sz[v] > n/2) return find_cen(v,u,all);
return u;
}
void dfs(int u,int p,int l){
seq[cnt++] = u;
lv[u] = l;
P[0][u] = p;
for(int i=1;i<=18;i++) P[i][u] = P[i-1][P[i-1][u]];
for(auto v : adj[u]) if(v != p) dfs(v,u,l+1);
}
long long dis(int u,int v){
if(lv[u] < lv[v]) swap(u,v);
long long diff = lv[u] - lv[v], dist = 0;
for(int i=18;i>=0;i--) if((1<<i) & diff) dist += (1<<i), u = P[i][u];
if(u == v) return dist;
for(int i=18;i>=0;i--) if(P[i][u] != P[i][v]) u = P[i][u], v = P[i][v], dist += 2*(1<<i);
return dist + 2;
}
void A2(int u){
size(1,1);
int c = find_cen(1,1,n);
dfs(c,c,1);
for(int i=1;i<=n;i++) h2[seq[i]] = seq[(i+n/2-1)%n+1], ans2 += dis(seq[i],h2[seq[i]]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
adj[u].push_back(v), adj[v].push_back(u);
}
for(int i=1;i<=n;i++) h1[i] = i;
A1(1,1);
A2(1);
printf("%lld %lld\n",ans1,ans2);
for(int i=1;i<=n;i++) printf("%d ",h1[i]);
printf("\n");
for(int i=1;i<=n;i++) printf("%d ",h2[i]);
}
Compilation message
Village.cpp: In function 'int main()':
Village.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
Village.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d%d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 6 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 7 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 8 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 10 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 11 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 12 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 13 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 14 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 15 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 17 |
Correct |
2 ms |
10844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 6 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 7 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 8 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 10 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 11 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 12 |
Correct |
2 ms |
11096 KB |
Output is correct |
| 13 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 14 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 15 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 17 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 18 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 19 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 20 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 21 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 22 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 23 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 24 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 25 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 26 |
Correct |
2 ms |
10852 KB |
Output is correct |
| 27 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 28 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 29 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 30 |
Correct |
2 ms |
10844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 6 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 7 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 8 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 10 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 11 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 12 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 13 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 14 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 15 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 17 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 18 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 19 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 20 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 21 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 22 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 23 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 24 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 25 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 26 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 27 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 28 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 29 |
Correct |
2 ms |
11096 KB |
Output is correct |
| 30 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 31 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 32 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 33 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 34 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 35 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 36 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 37 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 38 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 39 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 40 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 41 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 42 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 43 |
Correct |
2 ms |
10852 KB |
Output is correct |
| 44 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 45 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 46 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 47 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 48 |
Correct |
63 ms |
16204 KB |
Output is correct |
| 49 |
Correct |
76 ms |
16868 KB |
Output is correct |
| 50 |
Correct |
58 ms |
16988 KB |
Output is correct |
| 51 |
Correct |
61 ms |
15788 KB |
Output is correct |
| 52 |
Correct |
58 ms |
16720 KB |
Output is correct |
| 53 |
Correct |
55 ms |
16316 KB |
Output is correct |
| 54 |
Correct |
40 ms |
16548 KB |
Output is correct |
| 55 |
Correct |
78 ms |
22864 KB |
Output is correct |
| 56 |
Correct |
76 ms |
19540 KB |
Output is correct |
| 57 |
Correct |
86 ms |
18744 KB |
Output is correct |
| 58 |
Correct |
70 ms |
17748 KB |
Output is correct |
| 59 |
Correct |
78 ms |
16884 KB |
Output is correct |
| 60 |
Correct |
53 ms |
17352 KB |
Output is correct |
| 61 |
Correct |
51 ms |
17228 KB |
Output is correct |
| 62 |
Correct |
54 ms |
17236 KB |
Output is correct |
| 63 |
Correct |
49 ms |
16980 KB |
Output is correct |
| 64 |
Correct |
64 ms |
17164 KB |
Output is correct |
| 65 |
Correct |
52 ms |
17236 KB |
Output is correct |
| 66 |
Correct |
49 ms |
16980 KB |
Output is correct |
| 67 |
Correct |
41 ms |
15444 KB |
Output is correct |
| 68 |
Correct |
42 ms |
16212 KB |
Output is correct |
| 69 |
Correct |
50 ms |
17260 KB |
Output is correct |
| 70 |
Correct |
48 ms |
16980 KB |
Output is correct |
| 71 |
Correct |
35 ms |
15196 KB |
Output is correct |
| 72 |
Correct |
50 ms |
15776 KB |
Output is correct |
| 73 |
Correct |
49 ms |
17232 KB |
Output is correct |
| 74 |
Correct |
46 ms |
16732 KB |
Output is correct |
| 75 |
Correct |
68 ms |
16776 KB |
Output is correct |
| 76 |
Correct |
56 ms |
16724 KB |
Output is correct |
| 77 |
Correct |
50 ms |
16952 KB |
Output is correct |
| 78 |
Correct |
38 ms |
14744 KB |
Output is correct |
| 79 |
Correct |
41 ms |
15528 KB |
Output is correct |
| 80 |
Correct |
63 ms |
16724 KB |
Output is correct |
| 81 |
Correct |
51 ms |
17052 KB |
Output is correct |
| 82 |
Correct |
59 ms |
17104 KB |
Output is correct |
