专栏文章

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

寻寻逍遥2006
P11824题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miq4c69q
此快照首次捕获于
2025/12/03 22:44
3 个月前
此快照最后确认于
2025/12/03 22:44
3 个月前
查看原文
原问题等价于对于每一个点 ii，求树上包含 ii 的所有树上独立集的最大点权之和。

测试点 1∼21\sim 2

暴力枚举派遣的队员的集合，如果其满足限制，则统计其贡献。
时间复杂度 O(2nn)O(2^nn)。

测试点 33

先考虑只求解 11 号点。
尝试计算对于 k=1,2…nk=1,2\dots n，包含 11 号点，且 vv 的最大值恰好为 kk 的独立集数量，考虑使用树形 DP：
设计 DP 状态 fi,j,0/1f_{i,j,0/1} 表示在 ii 的子树内，选择一个 vv 的最大值为 jj 的集合，且不包含/包含 ii 的集合数量。
求解 ii 点的状态时依次将每一个儿子 vv 合并。
具体的贡献形式有 fi,j,0×(fv,k,0+fv,k,1)→fi,max⁡(j,k),0f_{i,j,0}\times (f_{v,k,0}+f_{v,k,1})\to f_{i,\max(j,k),0}，fi,j,1×fv,k,0→fi,max⁡(j,k),1f_{i,j,1}\times f_{v,k,0}\to f_{i,\max(j,k),1}。
单次合并时枚举 j,kj,k，时间复杂度 O(n2)O(n^2)。
最终 11 号点的答案就是 ∑i=1nif1,i,1\sum\limits_{i=1}^nif_{1,i,1}，时间复杂度 O(n3)O(n^3)。
对于每一个点进行这一过程，时间复杂度 O(n4)O(n^4)。

测试点 4∼54\sim 5

上面的合并结构时 max⁡\max 卷积，考虑较为一般的形式：
hk=∑max⁡(i,j)=kfigjh_k=\sum\limits_{\max(i,j)=k}f_ig_j。
有 ∑k=1mhk=∑k=1m∑max⁡(i,j)=kfigj=∑max⁡(i,j)≤mfigj=(∑i≤mfi)(∑j≤mgj)\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)。
因此，我们对 ff 和 gg 求前缀和，对位相乘，然后再做差分，就可以得到 hh。
这样单次合并的复杂度可以优化至 O(n)O(n)，总时间复杂度优化到 O(n3)O(n^3)。

测试点 4∼54\sim 5 另解

考虑放宽限制，计算对于 k=1,2…nk=1,2\dots n，包含 11 号点，且 vv 的最大值至多为 kk 的独立集数量。
发现这时每一个点只有可以选择和不可选择两种状态，对于单个的 kk，可以直接树形 DP O(n)O(n) 解决。
求解一个点的答案时间复杂度为 O(n2)O(n^2)，总时间复杂度为 O(n3)O(n^3)。

测试点 6∼76\sim 7

考虑 kk 从小到大的过程，每一个点有且仅有一次从不可选择到可选择的变化，因此考虑使用数据结构维护 DP 值变化的过程，这就是经典的动态 DP 问题。
使用树剖线段树总时间复杂度为 O(n2log⁡2n)O(n^2\log^2n)，使用全局平衡二叉树时间复杂度为 O(n2log⁡n)O(n^2\log n)，但实现效率差距不大，可能需要卡常。

测试点 8∼98\sim 9

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

测试点 10∼1110\sim 11

注意到在上面的做法中，DP 状态第第二维实际上只与 viv_i 的值域有关，更本质得说，只与本质不同的 viv_i 的数量有关。
所以复杂度实际上是 O(Vn)O(Vn) 的，其中 VV 是本质不同的 viv_i 的数量。

满分做法

使用转置原理求解这个问题。
考虑这样一个问题：记 ai,ja_{i,j} 为包含点 ii 且 vv 最大的点为 jj 的独立集数量，那么记 nn 阶方阵 A=(ai,j)A=(a_{i,j})。记向量 a=[v1,v2…vn]⊤a=[v_1,v_2\dots v_n]^\top，则我们要求的就是向量 b=Aab=Aa。
考虑这个问题的转置，给每一个点设置一个额外的权值 wiw_i，记 a′=[w1,w2…wn]⊤a'=[w_1,w_2\dots w_n]^\top，考虑问题 b′=Aa′b'=Aa'。
这个问题就是：对于每一个 ii，求所有 vv 权值最大值等于 ii 的独立集的 ww 权值之和的和。
发现新问题是可以使用树剖线段树解决的。
考虑按照点的 vv 权值从小到大一次加入每一个点。
实时维护 fi,0/1f_{i,0/1} 表示在 ii 的子树内不包含/包含 ii 的情况下，可能的独立集数量和 ww 权值之和的和。
事实上 ff 是一个二元组 (cnt,val)(cnt,val)。
对其进行的加法和乘法运算分别为 (cnt1,val1)+(cnt2,val2)=(cnt1+cnt2,val1+val2)(cnt_1,val_1)+(cnt_2,val_2)=(cnt_1+cnt_2,val_1+val_2)，(cnt1,val1)×(cnt2,val2)=(cnt1×cnt2,cnt1×val2+cnt2×val1)(cnt_1,val_1)\times (cnt_2,val_2)=(cnt_1\times cnt_2,cnt_1\times val_2+cnt_2\times val_1)。
首先考虑转移：
fi,0=∏v∈soni(fv,1+fv,0),fi,1=opi∏v∈sonifv,0f_{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}。
其中 opiop_i 在 ii 还没有出现过是为 (0,0)(0,0)，在 ii 出现过之后为 (1,wi)(1,w_i)，单独将重儿子 uu 提取出来，此时记 sonison_i 为除 uu 之外的所有儿子，那么就可以得到矩阵转移：
[fi,0fi,1]=[∏v∈soni(fv,0+fv,1)∏v∈soni(fv,0+fv,1)op∏v∈sonifv,00][fu,0fu,1]\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}
不妨记这个矩阵为 BiB_i。每一次修改相当于修改一个点 uu 的 opop，考虑修改之后，矩阵 BB 会发生变化的位置只有 uu 到根的路径上跳轻边跳到的点，根据重链剖分的性质，这样个点只有 O(log⁡n)O(\log n) 个。
对于每一个节点建立维护 BB 矩阵中的两个连乘 ∏v∈soni(fv,0+fv,1)\prod\limits_{v\in son_i}(f_{v,0}+f_{v,1}) 和 ∏v∈sonifv,0\prod\limits_{v\in son_i}f_{v,0} 的线段树，这样就能够支持对于单个轻儿子的 ff 的修改。
同时对于每一条重链维护矩阵 BB 的线段树，这样边能够支持对于单个 BB 的修改以及链顶节点的 ff 值得查询。
具体的修改过程，就是根据计算出的 ∏v∈soni(fv,0+fv,1)\prod\limits_{v\in son_i}(f_{v,0}+f_{v,1}) 和 ∏v∈sonifv,0\prod\limits_{v\in son_i}f_{v,0} 的值更新新的 BuB_u。就可以通过整条链上面的矩阵来计算出新的 ftopu,0f_{top_u,0} 和 ftopu,1f_{top_u,1}，然后就可以更新 fatopufa_{top_u} 的线段树，以此类推一直更新到 f1,0f_{1,0} 和 f1,1f_{1,1}。
因此按照 vv 从小到大修改每一个 uu，每一次修改后 f1,0+f1,1f_{1,0}+f_{1,1} 的增加量就是所有包含 uu 且以 uu 为最大值的独立集数量以及重量之和。
假设每 ii 次修改之后 f1,0+f1,1f_{1,0}+f_{1,1} 的值为 lasilas_i。
那么对于第 ii 小的来说答案就是 lasi−lasi−1las_i-las_{i-1} 的第二维。
发现所有对于第二维的操作都是形如 ai←ai+aj×ka_i\gets a_i+a_j\times k 的操作，所以对其进行转置操作有 aj←aj+ai×ka_j\gets a_j+a_i\times k。
对于第二维的加法，都可以写成 val1←val1+val2val_1\gets val_1+val_2 的形式，因此转置之后有 val2←val1+val2val_2\gets val_1+val_2，减法同理。
对于第二维的乘法，可以写成 val3←val3+val1×cnt2+val2×cnt1val_3\gets val_3+val_1\times cnt_2+val_2\times cnt_1 的形式，因此转置之后有 val1←val1+val3×cnt2val_1\gets val_1+val_3\times cnt_2，val2←val2+val3×cnt1val_2\gets val_2+val_3\times cnt_1。
因此可以直接封装出所有操作的逆，然后倒序执行之前执行过的所有操作即可。
时间复杂度 O(nlog⁡2n)O(n\log^2n)，空间复杂度 O(nlog⁡n)O(n\log n) 或 O(n)O(n)。
可以将树剖线段树替换成全局平衡二叉树，将时间复杂度优化至 O(nlog⁡n)O(n\log n)，但实际效率差距不大。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...