CF1387B2 Village (Maximum) 题解

题意：

村里 \(n\) 个房子构成了一个 \(n\) 点 \(n-1\) 条边的树结构（下标从 \(1\) 开始），每条边长度均为 \(1\)。一开始每个房子里分别有一个村民。

现在所有村民都需要搬家（改变自己所在的点），搬家后依然需要满足每个房子里有且只有一个村民。也就是说，如果原本位于点 \(i\) 的村民搬到了点 \(v_i\)，那么应当满足：

对于任意点 \(i\)，有 \(i \neq v_i\)。

对于任意两个不同的点 \(i\) 与 \(j\)，有 \(v_i \neq v_j\)。

村民 \(i\) 搬家的花费是点 \(i\) 到点 \(v_i\) 的树上距离（即树上二点间相隔的边数），总花费为所有村民花费之和。求总花费的最大值及其方案。

输入格式：

第一行一个正整数 \(n\)，表示树的点数。

接下来 \(n-1\) 行每行二整数 \(a\) 和 \(b\)，表示树上有一条连接 \(a\) 和 \(b\)，长度为 \(1\) 的边。

输出格式：

第一行一个整数，表示总花费的最大值。

第二行 \(n\) 个整数 \(v_1 \dots v_n\)，表示搬家的方案：如果原本位于点 \(i\) 的村民搬到了点 \(v_i\)。

输出任意一组合法方案即可。

数据范围：

\(2 \leq n \leq 10^5,~1 \leq a,b \leq n\)

贪心地考虑每条边如何贡献尽可能多的经过次数，则不难发现边 \((u,v)\) 至多贡献 \(2 \cdot \min (\operatorname{size}(u), \operatorname{size}(v))\) 。

考虑如何构造能够达到这个最大值。首先我们以树的重心为根，然后将所有 \(u(u \le \left\lfloor\frac{n}{2}\right\rfloor)\) ，

与 \(u + \left\lfloor\frac{n}{2}\right\rfloor\) 配对。因为以重心为分界线的两棵子树均不超过 \(\left\lfloor\frac{n}{2}\right\rfloor\) ，则 \(u\) 和 \(u + \left\lfloor\frac{n}{2}\right\rfloor\) 位于不同子树内。

这样做为什么对呢？因为在此种匹配方式的构造中，左子树的任意 \(u,v\) 交换不会改变经过的边数（甚至是边）

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,rt,res,pos=1,mx[N],sz[N],dep[N],num[N],ans[N],head[N];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs1(int u,int f)
{
    sz[u] = 1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == f) continue;
        dfs1(v,u); sz[u] += sz[v]; up(mx[u], sz[v]);
    }up(mx[u], n - sz[u]);
    if(!rt || mx[u] < mx[rt]) rt = u;
}
void dfs2(int u,int f)
{
    static int tim = 0; num[++tim] = u;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == f) continue;
        dep[v] = dep[u] + 1; dfs2(v,u);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1, u,v; i < n; i++) {
        cin >> u >> v; addEdge(u,v); addEdge(v,u);
    } dfs1(1,0); dfs2(rt,0);
    for(int i = 1, u,v; i <= n / 2; i++)
    {
        u = num[i]; v = num[i + n / 2];
        res += (dep[u] + dep[v]) * 2;
        ans[u] = v; ans[v] = u;
    }
    if(n & 1)
    {
        int u = num[n], v = num[1], w = num[1 + n / 2];
        res += dep[u] * 2; ans[u] = v; ans[v] = w; ans[w] = u;
    }
    cout << res << '\n';
    for(int i = 1; i <= n; i++)
        cout << ans[i] << " \n"[i == n];
    return 0;
}