#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,pos[100001],ans_min,ans_max,st,sz[100001],mov[100001];
vector<int> adj[100001];
void dfs_min(int x, int par) {
for (auto s : adj[x]) if (s!=par) dfs_min(s,x);
if (pos[x]==x) {
if (x==st) swap(pos[x],pos[adj[x][0]]);
else swap(pos[x],pos[par]);
ans_min+=2;
}
}
int dfs_sz(int x, int par) {
sz[x]=1;
for (auto s : adj[x]) if (s!=par) sz[x]+=dfs_sz(s,x);
ans_max+=2*min(sz[x],n-sz[x]);
return sz[x];
}
int cen(int x, int par) {
for (auto s : adj[x]) if (s!=par && sz[s]>n/2) return cen(s,x);
return x;
}
vector<int> group[100001];
void dfs(int x, int par, int idx) {
group[idx].push_back(x);
for (auto s : adj[x]) if (s!=par) dfs(s,x,idx);
}
void sol_max() {
dfs_sz(1,0);
int centroid=cen(1,0);
for (int i=0; i<adj[centroid].size(); ++i) dfs(adj[centroid][i],centroid,i+1);
group[0].push_back(centroid);
vector<pii> v;
for (int i=0; i<=adj[centroid].size(); ++i) v.push_back(pii(group[i].size(),i));
sort(v.begin(),v.end());
int siz=v.size();
queue<int> q;
for (int i=0; i<siz-1; ++i) {
int n1=v[i].second, n2=v[i+1].second;
for (int j=0; j<group[n1].size(); ++j) swap(mov[group[n1][j]],mov[group[n2][j]]);
if (i!=siz-2) for (auto s : group[n1]) q.push(s);
}
for (int i=group[v[siz-2].second].size(); i<group[v[siz-1].second].size(); ++i) {
swap(mov[group[v[siz-1].second][i]],mov[q.front()]);
q.pop();
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n;
for (int i=1; i<=n; ++i) pos[i]=i, mov[i]=i;
for (int i=0; i<n-1; ++i) {
int a,b; cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i=1; i<=n; ++i) if (adj[i].size()>1) st=i;
dfs_min(st,0);
sol_max();
cout<<ans_min<<" "<<ans_max<<"\n";
for (int i=1; i<=n; ++i) cout<<pos[i]<<" ";
cout<<"\n";
for (int i=1; i<=n; ++i) cout<<mov[i]<<" ";
}
Compilation message
Village.cpp: In function 'void sol_max()':
Village.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i=0; i<adj[centroid].size(); ++i) dfs(adj[centroid][i],centroid,i+1);
| ~^~~~~~~~~~~~~~~~~~~~~
Village.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i=0; i<=adj[centroid].size(); ++i) v.push_back(pii(group[i].size(),i));
| ~^~~~~~~~~~~~~~~~~~~~~~
Village.cpp:50:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int j=0; j<group[n1].size(); ++j) swap(mov[group[n1][j]],mov[group[n2][j]]);
| ~^~~~~~~~~~~~~~~~~
Village.cpp:54:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i=group[v[siz-2].second].size(); i<group[v[siz-1].second].size(); ++i) {
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Runtime error |
7 ms |
9884 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5020 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5024 KB |
Output is correct |
4 |
Correct |
3 ms |
5028 KB |
Output is correct |
5 |
Correct |
4 ms |
5076 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
5024 KB |
Output is correct |
8 |
Correct |
3 ms |
4980 KB |
Output is correct |
9 |
Correct |
3 ms |
5032 KB |
Output is correct |
10 |
Correct |
3 ms |
5076 KB |
Output is correct |
11 |
Correct |
3 ms |
5076 KB |
Output is correct |
12 |
Correct |
5 ms |
5024 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5088 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
16 |
Correct |
3 ms |
5028 KB |
Output is correct |
17 |
Correct |
3 ms |
5076 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
3 ms |
5076 KB |
Output is correct |
20 |
Correct |
3 ms |
5076 KB |
Output is correct |
21 |
Correct |
4 ms |
5032 KB |
Output is correct |
22 |
Correct |
3 ms |
5076 KB |
Output is correct |
23 |
Correct |
3 ms |
5076 KB |
Output is correct |
24 |
Correct |
5 ms |
5076 KB |
Output is correct |
25 |
Correct |
3 ms |
4948 KB |
Output is correct |
26 |
Correct |
3 ms |
5076 KB |
Output is correct |
27 |
Correct |
4 ms |
5020 KB |
Output is correct |
28 |
Correct |
3 ms |
5076 KB |
Output is correct |
29 |
Correct |
3 ms |
5076 KB |
Output is correct |
30 |
Correct |
3 ms |
5028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Runtime error |
7 ms |
9884 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |