自动搬运

查看原文

来自洛谷，原作者为

	zhylj 人生输家

搬运于2025-08-24 22:25:45，当前版本为作者最后更新于2022-01-15 10:06:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑树的情况怎么做：一个经典套路是先找到重心（如果有两个重心并且以两个重心为根时的树同构，那么答案再 $\times 2$），然后把重心定为根，问题就被转化为了有根树，那么对于一个节点，可以把它的孩子中每个同构等价类的大小的阶乘乘起来贡献到答案。同构可以考虑通过树哈希来判断，即每个深度 $i$ 用一个哈希函数 $h_i(a)=\sum_j (a_j+1)b_i^j\bmod p$，其中 $b_i$ 为随机数，$p$ 为你喜爱的质数，$a_i$ 为所有孩子哈希值排完序后的结果。

接着考虑仙人掌，可以发现仙人掌同构等价于圆方树同构，于是先求圆方树并找到重心，然后从重心开始 DFS（注意到由于重心那一侧），分类讨论：

• 对于方点，若其为重心，那么它可以旋转，也可以翻折，我们要找出环上哈希值构成的序列（必须按照环的顺序）和它的反串的所有循环同构和原串相同的个数 $c$，那么它对答案贡献 $\times c$。
• 对于非重心方点，其父亲所在子树（也就是重心所在子树）的大小超过了 $\left\lfloor \dfrac n2\right\rfloor$，所以这个环必然不可能被旋转，但它依然可以翻折，所以若它是回文，那么对答案贡献 $\times 2$。
• 否则，依然根据孩子中同构的等价类大小的阶乘来对答案贡献。

需要注意的是，由于环可以翻折，但不能旋转，所以我们维护非重心方点的哈希值时，取的是孩子哈希值序列（注意我们必须按环的顺序排列这个序列）和它反串中字典序最小的一个来做哈希。

然后统计答案的时候不难发现是若干个阶乘之积，维护出每个阶乘的贡献然后做一个前缀和，对每个质数暴力统计就好了。

时间复杂度 $\mathcal O(n\log n)$。

代码链接（写的较丑，谨慎参考）。