自动搬运

查看原文

来自洛谷，原作者为

	寻逍遥2006 晓看天色暮看云，行也思君，坐也思君；春赏百花冬赏雪，醒也思卿，梦也思卿

搬运于2025-08-24 23:10:31，当前版本为作者最后更新于2025-02-27 21:59:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

原问题等价于对于每一个点 $i$，求树上包含 $i$ 的所有树上独立集的最大点权之和。

测试点 $1\sim 2$

暴力枚举派遣的队员的集合，如果其满足限制，则统计其贡献。

时间复杂度 $O(2^nn)$。

测试点 $3$

先考虑只求解 $1$ 号点。

尝试计算对于 $k=1,2\dots n$，包含 $1$ 号点，且 $v$ 的最大值恰好为 $k$ 的独立集数量，考虑使用树形 DP：

设计 DP 状态 $f_{i,j,0/1}$ 表示在 $i$ 的子树内，选择一个 $v$ 的最大值为 $j$ 的集合，且不包含/包含 $i$ 的集合数量。

求解 $i$ 点的状态时依次将每一个儿子 $v$ 合并。

具体的贡献形式有 $f_{i,j,0}\times (f_{v,k,0}+f_{v,k,1})\to f_{i,\max(j,k),0}$，$f_{i,j,1}\times f_{v,k,0}\to f_{i,\max(j,k),1}$。

单次合并时枚举 $j,k$，时间复杂度 $O(n^2)$。

最终 $1$ 号点的答案就是 $\sum\limits_{i=1}^nif_{1,i,1}$，时间复杂度 $O(n^3)$。

对于每一个点进行这一过程，时间复杂度 $O(n^4)$。

测试点 $4\sim 5$

上面的合并结构时 $\max$ 卷积，考虑较为一般的形式：

$h_k=\sum\limits_{\max(i,j)=k}f_ig_j$。

有 $\sum\limits_{k=1}^{m}h_k=\sum\limits_{k=1}^m\sum\limits_{\max(i,j)=k}f_ig_j=\sum\limits_{\max(i,j)\le m}f_ig_j=\left(\sum\limits_{i\le m}f_i\right)\left(\sum\limits_{j\le m}g_j\right)$。

因此，我们对 $f$ 和 $g$ 求前缀和，对位相乘，然后再做差分，就可以得到 $h$。

这样单次合并的复杂度可以优化至 $O(n)$，总时间复杂度优化到 $O(n^3)$。

测试点 $4\sim 5$ 另解

考虑放宽限制，计算对于 $k=1,2\dots n$，包含 $1$ 号点，且 $v$ 的最大值至多为 $k$ 的独立集数量。

发现这时每一个点只有可以选择和不可选择两种状态，对于单个的 $k$，可以直接树形 DP $O(n)$ 解决。

求解一个点的答案时间复杂度为 $O(n^2)$，总时间复杂度为 $O(n^3)$。

测试点 $6\sim 7$

考虑 $k$ 从小到大的过程，每一个点有且仅有一次从不可选择到可选择的变化，因此考虑使用数据结构维护 DP 值变化的过程，这就是经典的动态 DP 问题。

使用树剖线段树总时间复杂度为 $O(n^2\log^2n)$，使用全局平衡二叉树时间复杂度为 $O(n^2\log n)$，但实现效率差距不大，可能需要卡常。

测试点 $8\sim 9$

对于每一个点进行一次求解太麻烦了，发现 $4\sim 5$ 的两种做法都是可以使用换根 DP 进行求解，时间复杂度 $O(n^2)$。

测试点 $10\sim 11$

注意到在上面的做法中，DP 状态第第二维实际上只与 $v_i$ 的值域有关，更本质得说，只与本质不同的 $v_i$ 的数量有关。

所以复杂度实际上是 $O(Vn)$ 的，其中 $V$ 是本质不同的 $v_i$ 的数量。

满分做法

使用转置原理求解这个问题。

考虑这样一个问题：记 $a_{i,j}$ 为包含点 $i$ 且 $v$ 最大的点为 $j$ 的独立集数量，那么记 $n$ 阶方阵 $A=(a_{i,j})$。记向量 $a=[v_1,v_2\dots v_n]^\top$，则我们要求的就是向量 $b=Aa$。

考虑这个问题的转置，给每一个点设置一个额外的权值 $w_i$，记 $a'=[w_1,w_2\dots w_n]^\top$，考虑问题 $b'=Aa'$。

这个问题就是：对于每一个 $i$，求所有 $v$ 权值最大值等于 $i$ 的独立集的 $w$ 权值之和的和。

发现新问题是可以使用树剖线段树解决的。

考虑按照点的 $v$ 权值从小到大一次加入每一个点。

实时维护 $f_{i,0/1}$ 表示在 $i$ 的子树内不包含/包含 $i$ 的情况下，可能的独立集数量和 $w$ 权值之和的和。

事实上 $f$ 是一个二元组 $(cnt,val)$。

对其进行的加法和乘法运算分别为 $(cnt_1,val_1)+(cnt_2,val_2)=(cnt_1+cnt_2,val_1+val_2)$，$(cnt_1,val_1)\times (cnt_2,val_2)=(cnt_1\times cnt_2,cnt_1\times val_2+cnt_2\times val_1)$。

首先考虑转移：

$f_{i,0}=\prod\limits_{v\in son_i}(f_{v,1}+f_{v,0}),f_{i,1}=op_i\prod\limits_{v\in son_i}f_{v,0}$。

其中 $op_i$ 在 $i$ 还没有出现过是为 $(0,0)$，在 $i$ 出现过之后为 $(1,w_i)$，单独将重儿子 $u$ 提取出来，此时记 $son_i$ 为除 $u$ 之外的所有儿子，那么就可以得到矩阵转移：

$\begin{bmatrix}f_{i,0}\\f_{i,1}\end{bmatrix}=\begin{bmatrix}\prod\limits_{v\in son_i}(f_{v,0}+f_{v,1})&\prod\limits_{v\in son_i}(f_{v,0}+f_{v,1})\\op\prod\limits_{v\in son_i}f_{v,0}&0\end{bmatrix}\begin{bmatrix}f_{u,0}\\f_{u,1}\end{bmatrix}$

不妨记这个矩阵为 $B_i$。每一次修改相当于修改一个点 $u$ 的 $op$，考虑修改之后，矩阵 $B$ 会发生变化的位置只有 $u$ 到根的路径上跳轻边跳到的点，根据重链剖分的性质，这样个点只有 $O(\log n)$ 个。

对于每一个节点建立维护 $B$ 矩阵中的两个连乘 $\prod\limits_{v\in son_i}(f_{v,0}+f_{v,1})$ 和 $\prod\limits_{v\in son_i}f_{v,0}$ 的线段树，这样就能够支持对于单个轻儿子的 $f$ 的修改。

同时对于每一条重链维护矩阵 $B$ 的线段树，这样边能够支持对于单个 $B$ 的修改以及链顶节点的 $f$ 值得查询。

具体的修改过程，就是根据计算出的 $\prod\limits_{v\in son_i}(f_{v,0}+f_{v,1})$ 和 $\prod\limits_{v\in son_i}f_{v,0}$ 的值更新新的 $B_u$。就可以通过整条链上面的矩阵来计算出新的 $f_{top_u,0}$ 和 $f_{top_u,1}$，然后就可以更新 $fa_{top_u}$ 的线段树，以此类推一直更新到 $f_{1,0}$ 和 $f_{1,1}$。

因此按照 $v$ 从小到大修改每一个 $u$，每一次修改后 $f_{1,0}+f_{1,1}$ 的增加量就是所有包含 $u$ 且以 $u$ 为最大值的独立集数量以及重量之和。

假设每 $i$ 次修改之后 $f_{1,0}+f_{1,1}$ 的值为 $las_i$。

那么对于第 $i$ 小的来说答案就是 $las_i-las_{i-1}$ 的第二维。

发现所有对于第二维的操作都是形如 $a_i\gets a_i+a_j\times k$ 的操作，所以对其进行转置操作有 $a_j\gets a_j+a_i\times k$。

对于第二维的加法，都可以写成 $val_1\gets val_1+val_2$ 的形式，因此转置之后有 $val_2\gets val_1+val_2$，减法同理。

对于第二维的乘法，可以写成 $val_3\gets val_3+val_1\times cnt_2+val_2\times cnt_1$ 的形式，因此转置之后有 $val_1\gets val_1+val_3\times cnt_2$，$val_2\gets val_2+val_3\times cnt_1$。

因此可以直接封装出所有操作的逆，然后倒序执行之前执行过的所有操作即可。

时间复杂度 $O(n\log^2n)$，空间复杂度 $O(n\log n)$ 或 $O(n)$。

可以将树剖线段树替换成全局平衡二叉树，将时间复杂度优化至 $O(n\log n)$，但实际效率差距不大。