双连通性变换

piggy123 · 2025-06-02 15:07:11 · 算法·理论

双连通性变换不仅仅指 cxy 讲课里提到的部分，还可以进行简单的拓展。

具体地，设 G=\operatorname{Trans}(F)，其中 \operatorname{Trans} 表示一种双连通性变换，F,G 均为集合幂级数。则 G_{S} 可以表示将 S 划分为若干个不交子集 T_1,T_2,\dots,T_k，权值 \prod_{i=1}^k F_{S} 乘上将这些子集联通为一棵树边权乘积之和。

具体的求解即为：按编号从小到大（两端节点编号的 \max）加边，令 i 次加完边后级数为 p_i，每次确定一个包含 i 的连通块，删除与 i 相连的编号小于等于 i 的边后，会形成若干个连通块，这些连通块满足 p_{i-1} 的限制。于是令 [x^{S}]q_{i}=[i\notin S]p_{i-1}\operatorname{link}(i,S)，其中 \operatorname{link}(i,S) 表示 i 到 S 中连边的权值和。容易根据组合意义得到 p_i=p_{i-1}\exp(q_{i-1})。于是变换在 O(2^nn^3) 内实现。

逆向的变换也是一样的。比如注意到若令所有边权值为 1，该变换即边双连通-连通变换；若令所有边权值为 -1，该变换即边双连通-连通变换的逆向变换。组合意义可以考虑一条割边被算了几次。

应用：建造军营 II，题解见 cxy 课件。