其实很水的一道题...但感觉思路还是很神...总之我这个sb就是想不到...

题意：

无根树独立集同构计数。

vfk出的神题真是不能更神。

题解：

首先如果不考虑同构，那么是个经典的树形dp。

[tex]f[i][0][/tex]和[tex]f[i][1][/tex]分别表示i号点选或不选的独立集数量，然后转移就行了。

由于存在同构，我们先选取树的重心为根。如果有两个重心，新建一个根连向重心，最后根节点特判。

考虑[tex]n[/tex]个位置染[tex]m[/tex]种颜色不同构的方案数，我们从保证颜色递增的方面来考虑答案很显然是[tex]C_{n+m-1}^n[/tex]。

于是接下来就是要球出每个节点不同构的子树有哪些。

这个就是经典hash了。

求出子树的hash值，排序，用某种函数合在一起就行了。

吐槽：

废话不说直接上图。

第一轮省选那题给我的阴影我就不说什么了。

这一题我写的是每次乘一个质数然后加上hash值。

然后怎么改都WA。

然后我按照题解改成了从小到大排序，先乘质数，然后异或，然后加。

然后还是WA。

然后我按照题解把质数换成了233333333。

然后尼玛就A了...

唉命中注定被卡hash...