HDU 5622 KK's Chemical

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5622

题目翻译

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=669&pid=1003

题解

因为只有( n ) 条边,所以这张图的每一个联通块,一定是形如一个环+若干颗根节点在环上的树。
对于一个环,我们DP方案数。(F \left [ x \right ] \left [ 1 \right ] )表示x填1号颜色方案数,(F \left [ x \right ] \left [ 0 \right ] )表示它不填1号颜色方案数。
初始化
(F \left [ x \right ] \left [ 1 \right ] = 1)
(F \left [ x \right ] \left [ 0 \right ] = 0)
递推
(F \left [ x \right ] \left [ 0 \right ] = F \left [ last \right ] \left [ 1 \right ] \times \left ( M – 1 \right ) + F \left [ last \right ] \left [ 0 \right ] \times \left ( M – 2 \right ) )
(F \left [ x \right ] \left [ 1 \right ] = F \left [ last \right ] \left [ 0 \right ] )
如果在树上,那么树上的每个节点都会让答案( \times \left ( M – 1 \right ) )

代码