正解:虚树+树上dp

解题报告:

传送门!

首先解释一下题意趴,,,语文70pts选手已经开始看不懂题辣QAQ

大概就是个给一个图,求独立集方案,且保证图是联通的,边的数量最多只比点多10

首先思考如果边的数量=点的数量-1,也就是一棵树的时候怎么搞?

直接树上dp就好,f[i][0/1]:选/不选第i个点方案数,转移就f[i][0]=∏(f[son][0]+f[son][1]),f[i][1]=∏f[son][0]

然后考虑多的边怎么搞呢

从上面那个思路自然而然地可以考虑到,可以暴力枚举非树边的情况,然后一个个计算

这样就有80pts辣!

然后考虑怎么继续优化呢

思考之前我想先问个问题吼

想到这一步有麻油想到辣NOIp2018D2T3保卫王国昂,,,一样是强制几个点选/不选,一样是树上dp,转移方程有一部分区别但差别并不大

所以这里也可以用保卫王国的两个方法做了这题!