自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 22:28:02，当前版本为作者最后更新于2021-01-02 23:29:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

懒得推贪心咋做啊？

我们考虑将问题描述为线性规划，设集族 $\mathcal I$ 包含了所有的路径，那么我们无非要给每条路径 $S$ 赋予一个权值 $x_S$ 表示这条路径走了多少次，容易写出约束：

$$\forall u, \sum_{S\ni u} x_S=a_u$$

我们的目的就是最小化

$$\sum_{S\in \mathcal I} x_S$$

线性规划一般是用不等式表述的，所以我们先将前面的等式拆成两组不等式，就可以写成标准的形式：

$$\begin{matrix} & x_S \ge 0,\\ \mathrm{minimize} & \sum_{S\in \mathcal I} x_S, \\ \mathrm{s.t.} & \sum_{S\ni u} x_S &\ge & a_u & (s_u)\\ & \sum_{S\ni u} -x_S &\ge& -a_u & (t_u)\\ \end{matrix} $$

我们改写为其对偶线性规划，即变成

$$\begin{matrix} & s_u,t_u \ge 0,\\ \mathrm{maximize} & \sum_u a_u(s_u-t_u), \\ \mathrm{s.t.} & \sum_{u\in S} (s_u-t_u) &\le & 1 & (x_S)\\ \end{matrix} $$

不难看出，我们可以令 $b_u=s_u-t_u$，那么就相当于 $b_u$ 可任取，然后目标是最大化 $\sum a_ub_u$，满足约束

$$\forall S\in \mathcal I,\sum_{u\in S} b_u \le 1$$

根据线性规划的对偶定理，这两个问题的解是相等的，我们只需求解后者。

由此，我们可以自然地设计一个 DP：$f_{u,d}$ 表示 $u$ 这颗子树里从 $u$ 出发，$b$ 值之和最大的路径为 $d$ 时最大的 $\sum a_ub_u$。显然 $d \in \{0,1\}$。而 $b_u$ 只有三种必要的取值：$\{-1,0,1\}$。我们枚举各情况进行转移，即是一个 $\Theta(n)$ DP。

（不过这里有一个小疑点，就是为什么最优解一定是整数。容易发现本题的约束矩阵并不是全幺模的，因此不能套用该充分条件来说明。）