题目:https://www.lydsy.com/JudgeOnline/problem.php?id=5287

1、树简单dp环简单讨论

2、发现我们这个返祖边很少于是可以3^(m-n)来枚举 但是显然这样多余了 可以发现状态一共是(0,1)(1,0)(0,0) 对于一对返祖边来说只有这些状态  接着又发现(0,1)(0,0) 其实i是一种状态 于是2^(m-n)枚举再暴力dp即可

3、发现这样过不去 为什么 因为暴力dp的时候有很多重复的状态

怎么办 考虑将那些被返祖边包含的点提取出来 建虚树

 

提前预处理出dp转移时候的系数 然后再dp的时候只需要这虚树上的有限的点即可

设k[x][0] k[x][1]分别表示x节点 状态是0或者1 他们对于下一个虚树节点的转移系数分别是多少tr0,tr1就是真正虚树的下一个节点到我这里的转移了

遇到不是虚树上的节点 就把他的系数加进去 遇到虚树节点 就重置

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论