自动搬运

查看原文

来自洛谷，原作者为

	Cute_M 天真的以为自己还有一年的小【数据删除】最后还是承认了自己即将退役的事实。

搬运于2025-08-24 23:03:39，当前版本为作者最后更新于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))$。