[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$ 同时开大时限了（误）。

细节没懂的可以看代码。