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;
}