[P10717]【MX-X1-T5】「KDOI-05」简单的树上问题

· · 题解

讲一个神秘的（如）爆标做法。复杂度为 O(n4^kk^2)

首先定 1 为根，考虑 dp，f_{u,S1,S2} 代表在 u 的子树里，S1 集合中的虚树经过 u\rightarrow fa_u 的边，S2 集合中的虚树完全在 u 的子树内，此时的概率与 u 子树中点的贡献的乘积。因为 S1 与 S2 无交集，所以 (S1,S2) 可以被状压成一个 k 位三进制数。

接下来考虑怎么合并一个点的所有子树，先不考虑 u 这个节点是否被选择，发现我们对于第 i 选点只有四种情况：i 不在任何一个子树的 (S1,S2) 中，i 在恰好一个子树的 S1 中，i 在多于一个子树的 S1 中，i 恰好在一个子树的 S2 中。我们把四种状态分别记为 0/1/2/3，用 k 位四进制数状压，然后每次新加入一个子树进行合并，对每一位枚举转移情况，去掉不可能的转移可以做到 O(n8^k)。

考虑到不存在，恰好一个的条件总是比多于一个更好的，于是考虑把情况 2 改写为存在一个子树的 S1 中有 i，把这四个值求出来之后再用类似 iFMT 的方式逐位容斥回原本的形式，容斥中要对这一位为 2 的值减去这一位为 1 的值。

考虑这四个值怎么求，恰好一个的限制容易联想到子集卷积，而存在的限制有容易联想到或卷积。但这两者都提示我们去使用类似 FMT 的做法，同时使用子集卷积中占位多项式的思想。我们对于每一个四进制数的位置映射到一个占位多项式为 h_Sx^{i}，其中 h_S 为 S 位置当前的值，i 为 S 中 1,3 的个数。卷积时先做一遍变体的 FMT，也就是枚举每一位，这一位为 1/2/3 的分别加上这一位为 0 的多项式，然后对位相乘，最后 iFMT 回去。

接下来考虑如何把 f_u 数组改成卷积上 g 的形式。显然对于 g_S，考虑 S 每一位，若第 i 位为 0 则不在 S1,S2 中，若为 3 则在 S2 中，否则在 S1 中。

最后考虑如何把卷积出来的结果转化为到 f 的值。也就是如何确定 u 出现的集合，以及如何给一棵虚数“封顶”，前者还是可以逐位确定，注意这时 u 上的 1 可以直接将情况 0 转化为情况 2，后者能封顶当且仅当处于情况 2，然后就做完了。

为什么说（如）爆标呢？因为 k \le 8，O(4^kk^2) 的子集卷积好像还真跑不过只 FMT 状态 2，剩下部分暴力 O(6^k) 子集卷积，甚至要精细实现才能通过本题。该出加强版 k \le 10 同时开大时限了（误）。

细节没懂的可以看代码。

提交记录 O(n4^kk^2)

提交记录 O(n6^k)