主要思路

刚看这题我人都是懵的…仔细看了看能大概想到，定一个根然后做 DP 得到方案，然后对于相同形态的子树进行方案分配即可。（但是不会写）

具体而言，转换成有根树的方法就是用重心来做根（如果有两个重心的话，就加一个虚根），并且每次 DFS 完之后用 Hash 值排序，然后进行分组转移。

转移的时候，可以给每一种情况进行标号，然后用前缀的组合意义来做转移即可。具体：\( dp[i] = \sum_{uniqueType \in subtree} {dp[uniqueType] + |subtree| – 1 \choose |subtree|} \)。

如果加了虚点，那就判一下就好了。