#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, ans[100005], resx;
vector<ll> adj[100005];
pair<ll, ll> S(ll x, ll y){
vector<pair<ll, ll> > a;
a.clear();
pair<ll, ll> b;
for(int i = 0; i < adj[x].size(); i++){
if(adj[x][i] != y){
b = S(adj[x][i], x);
if(b.first == b.second) a.push_back(b);
}
}
if(a.size() == 0){
if(y == 0){
ans[b.second] = x;
ans[x] = b.first;
resx += 2;
return {0, 0};
}else return {x, x};
}else{
a.push_back({x, x});
ll m = a.size() - 2;
for(int i=0;i<=m;i++){
ans[a[i].first] = a[i + 1].first;
resx += 2;
}
res[x] = a[0].first;
return {x, a[m].first};
}
}
int main(){
cin >> n;
for(int i=1;i<n;i++){
ll u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
S(1, 0);
cout << resx << ' ' << 0 << '\n';
for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
cout << '\n';
for(int i = 1; i <= n; i++) cout << i << ' ';
cout << '\n';
}
Compilation message
Village.cpp: In function 'std::pair<long long int, long long int> S(long long int, long long int)':
Village.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i = 0; i < adj[x].size(); i++){
| ~~^~~~~~~~~~~~~~~
Village.cpp:32:9: error: 'res' was not declared in this scope; did you mean 'resx'?
32 | res[x] = a[0].first;
| ^~~
| resx
