题解：P11824 [湖北省选模拟 2025] 团队协作 / team

· · 题解

原问题等价于对于每一个点 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 卷积，考虑较为一般的形式：

有 $\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)。

首先考虑转移：

其中 $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)，但实际效率差距不大。