显然要自底向上进行\(dp\)
深度相同的子树结构相同所以可以利用深度来代表子树。
那么就应该统计出有向路径的个数。
考虑路径由链所拼成。那么状态里应该有有向链的条数。
设\(f_{i,j}\)表示深度为\(i\)链条数为\(j\)的方案数。
不选当前的节点则\(f_{i,j}=f_{i-1,k}\cdot f_{i-1,j-k}\)
若当前节点自成一链则\(f_{i,j}=f_{i-1,k}\cdot f_{i-1,j-k-1}\)
若当前节点和其他链构成一链\(f_{i,j}=f_{i-1,k}\cdot f_{i-1,j-k}\cdot 2k\)
通过当前节点连接两条链\(f_{i,j-1}=f_{i-1,k}\cdot f_{i-1,j-k}\cdot k\cdot (k-1)\)