树的计数
有根树数量=无根树数量*n
- 带标号无根树计数 \(\leftrightarrow\) Prufer序列
- 在无根树集合T与长为n-2，值为1-n的所有序列S 之间建立一一映射
- 树T映射到S，设T中节点度为\(d_i\)，S中i的出现次数为\(a_i\)，则有\(d_i=a_i+1\)
- 其本质上是说，对于无根树，每个节点的度数是可以任意分配的，且每个节点度数都确定的无根树个数可以统计
- [ByteCamp2021/Day1/B] Build The Trees
- 无标号无根树计数 \(\leftrightarrow\)?? 树的同构、树哈希
带标号树计数的DP方法
一般设DP状态为\(dp[i][j]\)表示，\(i\)个点的树，深度/etc为\(j\)?的有根树的个数。计算\(dp[i][j]\)?时，考虑删除树中根节点连接的unique的一个子树。unique一般可定义为包含最小编号节点的那个子树。在树有其他要求时可用其他定义。例如，树要求深度最大的子树只有一个，那就可以将unique定义为深度最大的子树。