CF1097G Vladislav and a Great Legend

发表于 分类于 ， ， 阅读次数：

题意：给出一棵有 个节点的树 。对于非空点集 ，设 为包含 中每个节点的最小连通子树的最小边数。

求：

答案对 取模，，，时限 。

注意到 很小，可以用斯特林数把幂拆成组合数，并利用组合意义。

  • 引理：

只需对每个 求出。 该式的组合意义是：所有非空点集的点集虚树中，选 条边的方案数之和。

考虑 DP。设：

  • ：考虑 子树内的所有非空点集 ， 的虚树最浅点为 ，且在虚树中选出 条边的方案数。

  • ：考虑 子树内的所有非空点集 ，令目前区域为 的虚树，在这个区域中选出 条边的方案数。

就是答案。（每个虚树会在其最浅点被统计）

边界：对于叶节点 ，只有 一种集合，（选或不选边 ）

转移：

  • 虚树的根是 点

    选择的点集必须跨越 “ , 各个子树” 中的至少两个。即交叉贡献。

    这部分方案可以向 贡献。

    假设目前正在合并分支 ：

  • 虚树的根不是 点

  • 最后加入边

根据树上背包，复杂度 。