多叉树题解

思路

条件要求每条父子边上父亲的标号更大，因此这道题是在统计树形偏序的线性扩展。

设以节点 $u$ 为根的子树大小为 $s_u$。树的递减标号数满足树形钩长公式

由于 $n<998244353$，所有 $s_u$ 在模意义下都可逆。

做法

先说明公式。根节点必须取得全树最大标号。删除根以后，各棵儿子子树内部仍需满足相同条件，而不同子树所使用的标号集合可以任意交错。若儿子子树大小依次为 $s_1,s_2,\ldots,s_k$，先用多项式系数选择各子树得到哪些标号，再乘各子树内部的合法方案数。对这条递推反复展开，所有阶乘项消去后恰好得到 $n!/\prod s_u$。

输入保证父亲编号小于儿子编号，因此可以按编号从大到小处理。初始每个节点的子树大小为一，把当前节点的子树大小累加到父亲即可在线性时间求出全部 $s_u$。同时计算 $n!$ 和所有子树大小的乘积，最后对乘积求一次模逆元。

第一个子任务可以枚举所有排列并逐边检查。第二个子任务可以按标号从小到大放置节点，使用子集动态规划：只有当一个节点的全部儿子都已经放置时，才能放置这个节点。满分算法使用上述树形钩长公式。

复杂度

求子树大小和两个乘积均为 $O(n)$，一次快速幂求逆为 $O(\log 998244353)$。总时间复杂度为 $O(n+\log 998244353)$，空间复杂度为 $O(n)$。