写这个套路题只是为了练手 / 借机会整改一下大多项式模板。
直接考虑点分治。
对于当前的一棵子树,考虑求出 fi 表示这棵子树的根往下延伸的所有路径中,费用等于 i 的方案数。
考虑怎么求这个。首先 DFS 求出 gi 表示这棵子树的根往下延伸的所有路径中,长度为 i 的条数。
那么有 fi=n−1∑j=i(ji)gj
其中 n 为次数界。
稍微推一下可得 i!fi=n−i−1∑j=01j!⋅(i+j)!gi+j
容易构造卷积形式计算。
求出 fi 后,将子树按最大深度排序逐个执行 NTT 合并。
总复杂度 O(nlog2n)。
代码:
1 |
|