【題解】Codeforces 1387B2. Village (Maximum)

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
const int maxn = 100005;
int n, a, b, ans[maxn], idx, mid1, mid2;
long long cnt;
vector <int> v[maxn], l;
 
int dfs(int x, int pre){
    int mx = 0, tot = 0, ret;
    for (auto i:v[x]){
        if (i == pre) continue;
        ret = dfs(i, x);
        mx = max(mx, ret);
        tot += ret;
    }
    mx = max(mx, n-tot-1);
    tot++;
    if (mx <= n/2){
        if (!mid1) mid1 = x;
        else{
            mid2 = x;
            cnt += n;
        }
    }
    else cnt += tot*2;
    return tot;
}
 
void dfs2(int x, int pre){
    for (auto i:v[x]){
        if (i == pre) continue;
        dfs2(i, x);
    }
    l.push_back(x);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1, 0);
    cnt = 0;
    int tmp = mid1;
    mid1 = 0;
    dfs(tmp, 0);
    if (mid2){
        dfs2(mid1, mid2);
        dfs2(mid2, mid1);
    }
    else dfs2(mid1, 0);
    tmp = (n)/2;
    for (int i = 0; i < n; i++){
        ans[l[i]] = l[(i+tmp)%n];
    }
    cout << cnt << "\n";
    for (int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
    cout << "\n";
}