题解：CF1799H Tree Cutting

_O_v_O_ · 2026-11-12 23:12:56 · 题解

来个 O(n^23^k) 但是根本卡不到上界的做法，欢迎来卡。

首先令 s_0=n，然后 a_i=s_{i-1}-s_i，那么现在转化为了要删大小 a_i 的连通块。

最后是一个连通块，所以考虑对连通块计数，枚举代表元 x，那么要删掉的部分为 x 子树外加上 x 子树内的部分子树。

令 siz_x 为 x 的子树大小，考虑有多少组方案能通过一个操作集合删掉一个子树，设 g_{x,S} 表示通过 S 删掉 x 子树的一部分（可能是全部）的方案数，转移为 g_{x,S}=\sum_{S_1\cap S_2\cap\cdots\cap S_k,S_1\cup S_2\cup \cdots\cup S_k=\varnothing}\prod_{1\le l\le k} g_{l,S_l}，即将 S 中的操作分配到儿子中去，于是可以枚举子集做到 O(n3^k) 完成该部分。

回到枚举代表元部分，考虑子树外咋删，显然可以同理，且我们只需要重算 x 到根路径上的 g。

所以做完了，我们合并 x 子树内和子树外的 g 即可，注意子树外的 g_{*,S} 需要满足 \sum_{i\in S} a_i=n-siz_x，也就是说，n-siz_x 无法被表示的话那算这个没意义，所以我们可以在这里剪枝。尽管理论是 O(n^23^k) 但根本卡不满。

应该可以用一个形如回退背包的东西优化到 O(n3^k)。

submission