Luogu4827 [国家集训队] Crash 的文明世界

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

题意：给出 个点的树 ，对于每个点 ，求 答案对 取模，，，时限 。

允许我们用第二类斯特林把 次方拆成组合数，后者有更好的组合性质。 于是，我们只需对于每个 求出

先考虑如何对根求解。使用树形 DP，记 在的子树内 转移时，儿子 对 贡献，对于 子树中的 ，有 ，即 在的子树内在的子树内在的子树内 综上： 是的儿子 特殊地，。

复杂度 。这样可以得出根的答案。

换根 DP 即可得到所有点的答案。转移的逆操作很简单，把加号改成减号就好。