给出一个个点条边无向图,求染色方案数(相邻点异色).
染色数是 NPC 的.注意到的条件.常规思路是理解为一棵树加上若干条非树边,但这并不能方便地处理染色问题.
问题转化:对于一条边,设分别表示同色和异色时边的权值.初始时.图的权值是边权之积.那么问题转化为求所有染色情况下的图的权值之和.
对于度数为点,假设他连到了,那么可以直接删掉它,最后答案乘上.实际上,应该是答案乘上.
有一个小细节:如果删除后出现了重边,那么应该把两条边合并,权值则是和分别相乘.
这样图中就只剩下了度及以上的点.即.又因为,可以得到.