【题解】P4395 Gem 气垫车

幽灵特工 · 2021-09-15 15:56:51 · 题解

这里有权值上界的正确证明

小学生秒懂系列。

欢迎进入 blog 查看你的小学生秒懂系列都更新了啥。

思路

先说思路。树形 DP，设 dp[x][i] 表示节点 x 的权值为 i 时，以 x 为根的子树权值和的最小值。对每个节点枚举权值 1...3 ，取最小值转移。

权值上界证明

本文主要是权值上界证明，题目做法部分到此结束。在证明权值上界为什么是常数 3 之前，先说明为什么不是 \log n+1 或者 4。

简要对题解区的 \log n+1 的说法证伪：AlanSP 认为“权值是跟层数是一个数量级的”。然而事实并非如此，对于一棵树，每一层仅和它的上一层和下一层关联，第 i 层的节点与第 i+2 或 i-2 层互不干扰，即权值可相同。这说明权值和层数不是一个数量级，还隐含了权值上界是常数 3 这一结论。

网上有人用 四色定理 ^1 得出本题权值上界为 4。这样得到的是一个宽松的上界，因为任意三个多边形可能会两两有公共边，而树中任意三个节点不会双连通。四色定理任意图形的限制放宽了上界，而正如我们接下来将看到的，实际上界会更紧。

现在证明权值上界是 3。

首先证明存在上界。对于题目这显然成立，优化最小值使得权值不可能为无限大。

假设上界 > 3，则存在四个节点使得其权值两两不同。由题意得，权值不同的充分条件是两节点有边相连。在优化最小值的前提下，如果这四个节点不是两两有边相连的，必定可以将至少一个节点的权值替换为更小值。因此这四个节点两两相连，不构成树，与题面矛盾。故假设不成立。

假设上界 <3，则可以举出如下反例 ^2:

显然节点1和2权值取2和3时树总价值最小。

既然上界不能大于3，也不能小于3，那就只好等于3了。证毕。

注释