#include <iostream>
#include <algorithm>
#include <vector>
#include <assert.h>
#define vi vector<int>
#define pub push_back
using namespace std;
int n;
vi adj[100001];
int res[100001], dp[100001][2], k = 0;
int mtcW[100001];
int res2[100001], sub[100001];
long long k = 0;
vector<vi> ord;
void dfs(int u, int p)
{
dp[u][0] = dp[u][1] = 0;
int ret = 0;
for (auto v : adj[u])
{
if (v != p)
{
dfs(v, u);
ret += dp[v][1];
}
}
dp[u][0] = ret;
for (auto v : adj[u])
{
if (v != p)
{
assert(dp[v][1] >= dp[v][0]);
dp[u][1] = max(dp[u][1], 1 + ret - dp[v][1] + dp[v][0]);
}
}
}
void bktrk(int u, int p, int s)
{
if (dp[u][s] == 0 && res[u] == -1)
{
res[u] = res[p];
res[p] = u;
}
if (s)
{
int ret = 0, spc = -1;
for (auto v : adj[u])
{
if (v != p) {ret += dp[v][1];}
}
for (auto v : adj[u])
{
if (v != p)
{
assert(dp[v][1] >= dp[v][0]);
if (1 + ret - dp[v][1] + dp[v][0] == dp[u][1])
{
spc = v;
res[spc] = u;
res[u] = spc;
break;
}
}
}
for (auto v : adj[u])
{
if (v != p) bktrk(v, u, (spc != v));
}
}
else
{
for (auto v : adj[u])
{
if (v != p) {bktrk(v, u, 1);}
}
}
}
void computeSub(int u, int p)
{
sub[u] = 1;
for (auto v : adj[u])
{
if (v != p)
{
computeSub(v, u);
sub[u] += sub[v];
}
}
}
int findCentroid(int u, int p, int o)
{
for (auto v : adj[u])
{
if (v != p && sub[v] > sub[o] / 2) return findCentroid(v, u, o);
}
return u;
}
void dfs2(int u, int p)
{
sub[u] = 1;
if (p == -1) ord.push_back(vi());
ord.back().push_back(u);
for (auto v : adj[u])
{
if (p == -1) ord.push_back(vi());
if (v != p)
{
dfs2(v, u);
sub[u] += sub[v];
k += 2 * sub[v];
}
}
}
bool comp(const vi &a, const vi &b) {return a.size() < b.size();}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) res[i] = -1;
for (int i = 1; i < n; i++)
{
int u, v; cin >> u >> v;
adj[u - 1].push_back(v - 1);
adj[v - 1].push_back(u - 1);
}
dfs(0, -1);
bktrk(0, -1, 1);
computeSub(0, -1);
int c = findCentroid(0, -1, 0);
dfs2(c, -1);
sort(ord.begin(), ord.end(), comp);
int j = ord.size() - 1, p = 0;
for (int i = 0; i < ord.size(); i++)
{
for (int i2 = 0; i2 < ord[i].size(); i2++)
{
res2[ord[i][i2]] = ord[j][p++];
if (p == ord[j].size()) {j = (j + 1) % ord.size(); p = 0;}
}
}
cout << 2 * (dp[0][1] + n - 2 * dp[0][1]) << " " << k << "\n";
for (int i = 0; i < n; i++)
{
cout << res[i] + 1;
if (i + 1 < n) cout << " ";
}
cout << "\n";
for (int i = 0; i < n; i++)
{
cout << res2[i] + 1;
if (i + 1 < n) cout << " ";
}
cout << "\n";
return 0;
}
Compilation message
Village.cpp:14:11: error: conflicting declaration 'long long int k'
14 | long long k = 0;
| ^
Village.cpp:11:33: note: previous declaration as 'int k'
11 | int res[100001], dp[100001][2], k = 0;
| ^
Village.cpp: In function 'int main()':
Village.cpp:144:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for (int i = 0; i < ord.size(); i++)
| ~~^~~~~~~~~~~~
Village.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i2 = 0; i2 < ord[i].size(); i2++)
| ~~~^~~~~~~~~~~~~~~
Village.cpp:149:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | if (p == ord[j].size()) {j = (j + 1) % ord.size(); p = 0;}
| ~~^~~~~~~~~~~~~~~~
