洛谷P14671 [ICPC 2025 Seoul R] Clean Arrangement 题解
洛谷P14671 [ICPC 2025 Seoul R] Clean Arrangement 题解
题面链接：P14671 [ICPC 2025 Seoul R] Clean Arrangement
题目描述（简化版）
给出一棵 \(n (2\le n \le 5000)\) 个节点的树，根节点为 \(1\) 。
让你把所有节点映射到 \(1\sim n\) 的整数数轴上，边 \((u,v)\) 的新长度就是数轴上 \(u\) 和 \(v\) 的差的绝对值。
要求最小化所有边的边长和，并且边不能交叉、不能覆盖根节点（比如下图的图三就是不合法的）。
图一和图二是题目的样例2的解法。
输入格式
第一行输入 \(n\) ，接下来 \(n-1\) 行每行输入两个数 \(u,v(1\le u,v \le n)\) 表示存在一条边 \((u,v)\) 。
输出格式
一行，答案。
可以去 Csacademy 画一下然后玩玩看，很容易就能看出这个题怎么做了。
首先，像图三这种红线很明显是亏的，数轴有的是空间，你干什么放到这么远的地方去呢？
进一步地，对于每个节点 \(u\) ，它的每个儿子 \(v\) 及其子树，最后肯定是扔在 \(u\) 的左右两侧的。
考察每个节点 \(u\) 如何计算贡献。方便期间，我们假设父节点 \(\mathtt{fa}(u)\) 在数轴上位于 \(u\) 右侧，毕竟反过来是同理的。
如果我们将 \(u\) 的某个子节点 \(v\) 和以 \(v\) 为根的子树的按其最佳方案扔到 \(u\) 的右侧，
那么边 \((u,\mathtt{fa}(u))\) 的长度会增加 \(\mathtt{size}(v)\) ，这里 \(\mathtt{size}(v)\) 表示以 \(v\) 为根节点的子树的节点总数。
因此我们会尽可能将 \(u\) 的子树扔到左侧，也就是尽量不扔到 \(u\) 和 \(\mathtt{fa}(u)\) 之间的那段区域。
不过无论将子树扔到哪一侧、扔多少，对于同一侧的每个节点 \(v_i\) ，边 \((v_i,u)\) 都会根据 \(v\) 的排序产生贡献
具体地，如果扔到 \(u\) 左侧的 \(v_i\) 从左到右依次是 \(v_1,v_2,\cdots,v_m\) ，那么对边长 \(\sum w(u,v_i)\) 的贡献为 \[ 1 + \mathtt{size}(v_m) + (\mathtt{size}(v_m) + \mathtt{size}(v_{m-1})) + \cdots + \left(\sum_{i=2}^{m}\mathtt{size}(v_i)\right) \] 也就是 \[ 1 + \sum_{i=1}^{m}\mathtt{size}(v_i)\times(i-1) \] 可以发现，离 \(u\) 越近的子节点（子树）贡献的次数越多，那么我们肯定希望越近的子树越小越好。
别忘了，我们还能花费 \(\mathtt{size}(v)\) 选择将一棵子树扔到右边去（\(u\) 和 \(\mathtt{fa}(u)\) 之间），不过这样亏吗？
考虑对 \(v_i\) 按 \(\mathtt{size}(v)\) 从大到小排序，于是 \(v_1\) 和子树肯定是放在左边的，现在考察 \(v_2\) 和子树。
不算自带的 \(1\) 的话，扔在左侧最小贡献暂时是 \(\mathtt{size}(v_2)\) ，扔到右边也暂时是 \(\mathtt{size}(v_2)\) ，然后呢？
观察上面的贡献公式，当 \(m>2\) 时，贡献会成倍地增加，尽管 \(v_3\) 依然扔左侧，但 \(v_4\) 却只能扔右侧了。
继续观察会发现，这么从大到小、不停左右交替的扔，这样一直扔到的是花费最小的那个，考虑贪心。
这个正确性的证明怎么看都繁琐的很，既然规律很容易就能看出来，那有兴趣的读者可以自行尝试证明。
另外，这只是边长的贡献，还要加上子树已经算出来的最小花费，这个值不会根据 \(v\) 放 \(u\) 哪侧而改变。
不妨记 \(f(u)\) 是以 \(u\) 为根的子树的最小花费，记 \(g(u)\) 为 \(u\) 对边 \((u,\mathtt{fa}(u))\) 的贡献。
可以发现 \(v_i(i \ge 1)\) 对 \(u\) 的贡献为 \[ \begin{aligned} f(u) &\gets f(u) + \mathtt{size}(v_i)\times \left\lfloor\frac{i - 1}{2}\right\rfloor + f(v) + g(v) \\[8pt]g(u) &\gets g(u) + \mathtt{size}(v_i)\times[i \bmod 2\equiv0] \end{aligned} \] 别忘了 \(g(u) \gets g(u) + 1\) ，因为和父节点连边的边权最小就是 \(1\) 。
时间复杂度 \(O(n^2\log n)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int, int> pii;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e3 + 15))
#define Fi first
#define Se second
int n, tot, sz[N], f[N], g[N];
vector<int> vec[N];
pii son[N];
void dfs(int u, int fa)
{
sz[u] = 1;
for(auto v : vec[u]) if(v != fa) { dfs(v, u); sz[u] += sz[v]; }
tot = 0;
for(auto v : vec[u]) if(v != fa) { son[++tot] = {sz[v], f[v] + g[v]}; }
static auto cmp = [](pii x, pii y) { return x.Fi > y.Fi; };
sort(son + 1, son + 1 + tot, cmp); g[u]++;
rep(i, 1, tot)
{
f[u] += son[i].Fi * ((i - 1) / 2) + son[i].Se;
if(!(i & 1)) g[u] += son[i].Fi;
}
}
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;
rep(i, 1, n - 1)
{
static int u, v; cin >> u >> v;
vec[u].push_back(v); vec[v].push_back(u);
}
dfs(1, 0);
cout << f[1] << '\n';
return 0;
}参考文献：
![洛谷P14671 [ICPC 2025 Seoul R] Clean Arrangement 题解](/qwq/img/p150.webp)
