BOI '20 - Village (Maximum)

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> g;
vector<int> subtree;
void dfsSubtree(int node, int parent = 0) {
    subtree[node] = 1;
    for (int child : g[node]) {
        if (child != parent) {
            dfsSubtree(child, node);
            subtree[node] += subtree[child];
        }
    }
}

vector<vector<pair<int, int>>> components;
void dfsComponent(int node, int parent = 0, int depth = 0) {
    components.back().emplace_back(node, depth);
    for (int child : g[node]) {
        if (child != parent) dfsComponent(child, node, depth+1);
    }
}

int main() {
    int n; cin >> n;
    g.resize(1+n);
    for (int i = 0; i < n-1; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    subtree.resize(1+n);
    dfsSubtree(1);

    // find centroid
    int centroid = 1;
    for (bool going = true; going; ) {
        going = false;
        for (int child : g[centroid]) {
            if (subtree[child] > subtree[centroid]) continue; // parent
            if (2*subtree[child] > n) {
                centroid = child;
                going = true;
                break;
            }
        }
    }

    for (int child : g[centroid]) {
        components.emplace_back();
        dfsComponent(child, centroid, 1);
    }
    components.push_back({{centroid, 0}});
    int m = components.size();

    vector<int> destination(1+n);
    long long totalDist = 0;

    // if there are two centroids, biggest component will be towards the second centroid, and will contain half of the nodes in the graph
    int c1 = 0, p1 = 0, c2 = 0, p2 = n/2;
    while (p2 >= (int)components[c2].size()) p2 -= components[c2++].size();
    for (int i = 0; i < n; ++i) {
        auto [a, aDist] = components[c1][p1];
        auto [b, bDist] = components[c2][p2];
        destination[a] = b;

        totalDist += aDist + bDist;

        ++p1, ++p2;
        if (p1 == (int)components[c1].size()) c1 = (c1+1)%m, p1 = 0;
        if (p2 == (int)components[c2].size()) c2 = (c2+1)%m, p2 = 0;
    }
    cout << totalDist << endl;
    for (int i = 1; i <= n; ++i) cout << destination[i] << ' ';
    cout << endl;
    return 0;
}