题解：XXYX Binary Tree

· · 题解

写完这道题，跑了 372 ms。发现有一个跑了 12 ms 的，点进去一看，是 \Theta(N) 做法。那么我们就来解释一下 kostia244 老师的做法。

　　假设树是 \Gamma = (V, E)，以 r 为根，有分划 X \sqcup Y = V，且 Y 是一个独立集。假设 L 是全体叶子。我们可以直接通过式计算出 B, C：

B = |Y| - [r \in Y], C = 2 \cdot \left\lvert Y \cap L^\complement\right\rvert.

　　假设 r \in X。每一个 x \in Y \cap L^\complement 会强制其所有子节点 \in X。那么我们为了给出 B 的贡献，所强制的节点数是

f = \sum_{v \in Y \cap L^\complement} (v\ \text{作为叶子的子结点数}).

后文记这个 v 作为叶子的子结点数为 \ell(v)。那么我们希望 B - \dfrac C2 个叶子属于 Y，因此希望 f + B - \dfrac C2 \le |L|。如果 r \in Y，可以类似推理。

　　因此，我们的问题形式变为，求一个独立集 S \subseteq L^\complement，满足 |S| = K 且

\sum_{v \in S} \ell(v)

最小。这个最小值我们记作 w(K)。处理其的一个方法是 Lagrange 松弛。由于如果我们直接放宽 |S| = K 的限制最小值会变成 0，所以我们考虑每选一个会使值额外减少 \lambda，也就是我们最小化 \ell(v) - \lambda 的和，这时的问题记作 F(\lambda)。

　　现在我们说明，\lambda 有用的取值只会有 [0, 4]。这是因为：\lambda < 0 肯定还不如不选；而对于一个独立集 S，如果存在一个比 S 的元素个数更大的独立集，我们一定能够通过如下两种操作得到一个：

　　无论哪种，答案的变化量不会超过 4。这样，你 \ell(v) - \lambda 至少可以把 -4 的变化量变成 0。假设最优解 F^*(\lambda) 的 K 值为 K^*(\lambda)，通过下述凸性，可以证明，w(K) 可以通过：选取 \lambda 使得 K^*(\lambda) \ge K 且 \lambda 最小，则 w(K) = F^*(\lambda) - \lambda \cdot K。

　　下面，我们还要证明，w 是凸的。我们采用线性规划的方法：对于每个点，赋实数 x_u \in [0, 1]。要求对于每一个 (u, v) \in E，x_u + x_v \le 1。并考虑 \ell(v) x_v 的求和。由 Birkhoff 定理得，有一个最大值满足 x_k \in \{0, 1\}。于是我们得到了一个线性规划问题：

P : \operatorname*{minimize}\limits_{\substack{x \in \mathbb R^V \\ 0 \le x \le 1\\x_u + x_v \le 1\ (uv \in E)\\\sum x = K}}\sum_{v {\in V}} x_v \cdot \mathrm{cost}(v).

　　我们可以得到这样的对偶问题。

P^\vee : \operatorname*{maximize}\limits_{\substack{\forall v, \lambda \le \mathrm{cost}(v) + \sum y_{v?} + s_v \\ y \ge 0, s \ge 0, \lambda \in \mathbb R}} K \lambda - \sum_{e \in E} y_e - \sum_{v \in V} s_v.

　　s 取非 0 值对线性规划的限制紧，还会使欲最大化的值变小，因此毫无意义。取 s = 0。则由于 P 可行且有界，w(K) = \mathrm{val}(P) = \mathrm{val}(P^\vee)（强对偶定理）。可以发现 K \lambda 一看就很像我们刚才提到的 Lagrange 松弛，因此考虑固定 \lambda 看盛夏的最优化问题。考虑对内层问题 I 作对偶（由于式过多略去），可以直观地感受到可行域恰好就是 x \in \mathbb R^V , 0 \le x \le 1, x_u + x_v \le 1\ (uv \in E)（记为 H）。同时这个问题的权值可以通过计算得出等于

\min_{x \in H} \sum_{v \in V} (\mathrm{cost}(v) - \lambda) x_v.

　　与 Lagrange 松弛恰好等价！

　　因此

w(K) = \max_{\lambda \in \mathbb R} (F^*(\lambda) - \lambda K),

也就是一族关于 K 的一次函数的 \max，是凸的。这下，我们一并解决了为什么 w 是凸的，为什么 Lagrange 松弛是对的这两个问题。

　　上文提到，选取 \lambda 使得 K^*(\lambda) \ge K 且 \lambda 最小，则 w(K) = F^*(\lambda) - \lambda \cdot K。这根据上面的式子也是好解释的。而且 0 \le \lambda \le 4 使得我们只需要计算 F^*(\lambda) 五次。而每一次我们都可以简单地用树形 DP 计算。

　　至此，我们得到了一个时间复杂度为 \Theta(N) 的算法。

　　参考代码可以看 kostia 的，有一些包括但不限于 \lambda \leftrightarrow -\lambda 的小差距。