T3[ABC213G]Connectivity2题意：给定一张无向图\(G\)，将其删去\(0\) 条及以上的边构成一张新图，求对于所有点\(k\in(1,n]\)，使\(k\) 与\(1\) 连通的新图的个数。比较套路的一道状压DP。尽管刚开始思考毫无头绪。Step1.令\(f_S\)表示点集为\(S\)的连通子图的个数，\(

[ABC213G]Connectivity2题解套路的经典图上计数题。考虑枚举和\(1\)相连的子集\(S\)。答案显然由两部分构成，\(S\)集合和\(1\)相连的方案数\(f(S)\)和\(S\)对于\(G\)的补集所有的方案数\(g(S)\)。答案就是二者相乘。显然\(g\)更好处理。直接枚举集合的边即可

好好好。我们设当前处理\(i\)的答案，那么最后的图就可以分成两个部分：\(1\)所在的联通块和其他，根据乘法原理，答案就是它们二者方案的乘积。设\(f_s\)表示集合\(s\)中所有点联通时图的情况数，\(g_s\)表示集合\(s\)中所有点不一定联通时图的情况数，则有：\[ans_i=\sum\limits