P17851

Gaochenxi103_QAQ · 2026-11-10 15:49:14 · 题解

沙子卡常题，差评。

做法

考虑本题弱化版，允许 O(n\log n) 复杂度如何处理。笔者题解。

定义 dp_{u,i} 表示子树 u 内选择出 i 条不相交的路径的最大边权和，钦定 i>0 时 u 必选。

观察到这个路径选择收益是递减的，即从选 i 条提升到选 i+1 条带来的额外收益是不小于从选 i+1 条到选 i+2 条的。即 dp_{u}(i+1)-dp_u(i)\ge dp_{u}(i+2)-dp_{u}(i+1)，令 d_i=dp_u(i+1)-dp_u(i)。d_i 单调不增，故 dp_u 是上凸的。

合并子树 v 的时候有两种情况，一种是不考虑 v 然后直接做 (\max,+) 卷积合并。一种是 dp_u(i)=\max(dp_u(i),dp_{v}(i)+w)，注意到这个只等价于 dp_u(0) 和 dp_v(i) 合并的时候多了 w 的价值，于是在卷积前令 dp_u(0)=w，卷完之后 dp_u(0) 变回 0 即可。这样就完成了归一。

但让 dp_u(0)=w，相当于 d_0-w。这可能会导致 d_i 不在单调，也就是会影响 dp_u 的凸性。但如果我们令 v 的合并顺序是按照 w 从大到小的。那么 dp_u(0) 在赋值为 w 后依旧是上凸的。

::::info[证明] 要证 dp_u(0) 从 0\to w 后 dp_u(i) 依旧上凸。即证 d_0-w\ge d_1，d_0-d_1\ge w。

考虑使用数学归纳法。

考虑在合并第一个 v 的时候。dp_u(1) 只可能等于 dp_v(1)+w，同理 dp_u(2)=dp_v(2)+w，以此类推。此时 d_i=dp_v(i+1)-dp_v(i)，u 的 d_i 此时与 v 的 d_i 完全相同。

然后因为是 u 考虑的第一个儿子，所以没有之前的状态。所有非 0 状态要加上价值 w，dp_u(i)=dp_v(i)+w,i> 0。差分数组中等价于只有 d_0\gets d_0-w。此前 d_i 完全等于 v 的 d_i，满足 d_i\ge d_{i+1}。所以第一次操作后 d_0-d_1\ge w，之后的操作都满足 w 不大于第一次操作的。临时 d_0-w 不会让 d_0<d_1，单调性仍存在。