令 f[i][j] 表示 i层的树进行了j步的方案数 转移是这样的 看根节点 我们要把j的步去掉根本身的一步后 剩下的j-1步分配给自己的儿子 从而可以去掉根节点 成为了一个 变成4个 i-1层 k步的子问题。 合并的时候用类似背包的思想 从第一个儿子哪里拿k1 个 第二个k2个 第三个 k3个。。。 01背包维护 即可

FFT 做法： 在f[i][j] 中可以看到 令p_i(x)=sigma {f[i][j]*x^j} 即 f[i]的母函数 那么上述的转移可以看成 p_(i+1)(x)=x*[p_i(x)]^4+1 后k项的系数就是 f[i+1][k] 用FFT计算[p_i(x)]^4 可以把转移优化到 klogk