题解：P11032 『DABOI Round 1』Develop a Tree

Cute_M · 2024-09-09 17:32:41 · 题解

更新：修缮了该帖子中提到的明显错误。

观察比赛名称可以发现，因为 D 在第一位，所以 D 最简单（大雾）。

同学开场切 D，太强了。

仔细阅读题目要求：

请注意，加边时允许与原树边重边，但任意两条新加的边都不能重合。

即：若存在一种方案来划分原树使得其可以满足所有已知的边不会连在同一个部点内，则设左部点个数为 l，右部点个数为 r，答案即为 C^k_{l\times r}。

问题转化为怎样在 O(n) 的时间复杂度内求出每个子树中的方案。

容易发现，对于一个点，其只可能与与其深度差为 1 的点连边，则将奇数深度点化为左部点，偶数深度点划分为右部点即可。

注意组合数求解过程中 C^k_{l\times r}=\frac{A^k_{l\times r}}{A^k_k}，其中除法需要用乘法逆元完成。这里保证了 p_i 均为质数，就用费马小定理做了。

复杂度 O(n(k+\log p_i))。