题解：XXYX Binary Tree

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

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

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

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

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

最小。这个最小值我们记作 $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\}$。于是我们得到了一个线性规划问题：

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

　　$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$）。同时这个问题的权值可以通过计算得出等于

　　与 Lagrange 松弛恰好等价！

　　因此

也就是一族关于 $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$ 的小差距。