主要思路
刚看这题我人都是懵的…仔细看了看能大概想到,定一个根然后做 DP 得到方案,然后对于相同形态的子树进行方案分配即可。(但是不会写)
具体而言,转换成有根树的方法就是用重心来做根(如果有两个重心的话,就加一个虚根),并且每次 DFS 完之后用 Hash 值排序,然后进行分组转移。
转移的时候,可以给每一种情况进行标号,然后用前缀的组合意义来做转移即可。具体:\( dp[i] = \sum_{uniqueType \in subtree} {dp[uniqueType] + |subtree| – 1 \choose |subtree|} \)。
如果加了虚点,那就判一下就好了。
Continue reading →