题意：
给定一张图，选择一些点和一些边，使得割断任意没有选的边，被选中的点仍连通。对 \(10^9+7\) 取膜。
\(n \leq 5 \cdot 10^5\)
这篇题解会略讲缩边，详讲自己推 dp 状态与转移式的过程。
前置知识：桥（割边）、缩边。
感觉有些地方的逻辑绕了点，强制分了小段，希望能让阅读者看得更明白。
看到图和连通，立刻想到 tarjan。
割断一条没有选的边，选中的点仍连通，割非桥，整张图仍然连通。
把桥删掉，则整张图分成若干连通子图。可以把一张子图看成一个点，这样形成的新图上没有环，因为在环上的边都不是割边，那它就是一棵树。
设一个新点 \(i\) 中共有 \(cntp_{i}\) 个原图中的节点，\(cnte_{i}\) 条原图中的边。后面的点边均在新树上。
问题转化为：给定一棵树，每个点有 \((2^{cntp_i}-1) \cdot 2^{cnte_i}\) 种染色方式，每条边可以染色或不染色，问有几种染色方法，使得割断任意非染色边，所有染色点仍连通。
树上的问题相较图更好解决，因为转移方向固定为从儿子到父亲。那么显然，现在应该进行 dp。后面说的子树默认是根在 \(1\) 的情况。
什么在转移时会造成影响呢？考虑 \(u\) 和其儿子 \(v\)。当 \(v\) 子树中有点被染色时，这个点需要与 \(v\) 连通，且 \(v\) 需要与 \(u\) 连通，这是为了让 \(v\) 中的点与整棵树其余部分连通。否则，\(u\) 与 \(v\) 间的边属于可有可无。
因此，设出 \(dp_{u,0/1}\)，\(dp_{u,0}\) 强制 \(u\) 及其子树不选任意一个点（空）；\(dp_{u,1}\) 强制 \(u\) 及其子树选至少一个点，且所有被选的点与 \(u\) 连通（不空）。
现在来考虑如何计算答案。
常用的做法是把一个点集放到它们的 lca 处计算，但是，\(dp_{u,1}\) 只考虑了连通性，而没有在意是否恰好是 lca。容斥应该可行。但是另一个想法是强制一个算入答案的状态不被另一个状态包含。
为了说明，先对树做一遍前缀和，设 \(sum_i\) 为 \(i\) 及其子树中的边数和，包括被缩掉的边。容易看出 \(dp_{u,1} \cdot 2^{sum_1 – sum_u}\) 表示了所有点均位于 \(u\) 子树，且所有点与 \(u\) 连通时的情况数。
现在让一个情况不被另一个情况包含。注意到能统计到一个点集的点均在根到 lca 的链上，则统计时强制断掉 \(u\) 与其父亲间的连边，就不会出现这些点都与 lca 的某个父亲连通的情况，从而保证了一个情况不会被统计多次。
说人话，找到一个点集的 lca，顺着 lca 往根走，满足每一步走过的边都被染色，则我们将在走到的那个点上统计整个子集的贡献。
对答案的贡献说清楚了，接着来说 dp 的求法。
设现在位于 \(u\)，要把 \(dp_{v,0/1}\) 合并进 \(u\)，设 \(dp’_{u,0/1}\) 为没有合并入 \(v\) 前的情况。
\(dp_{u,0}\) 显然只能从 \(dp’_{u,0}\) 和 \(dp_{v,0}\) 推出，且连接 \(u,v\) 的边可有可无。
\(dp_{u,1}\) 可以从 \(dp’_{u,1}\) 处得到，此时 \(v\) 可以选择空或不空，空时中间边可有可无，否则必须有。
\(dp_{u,1}\) 也可以从 \(dp’_{u,0}\) 处得到，此时 \(v\) 必须非空，中间的边必须存在。
初始时该点对应所有边均可选可不选，点看是否要求非空而言。
结束。
AC 后去 infoj 翻了最短代码，深感自己写复杂了，居然 \(4\) 个 dfs……
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 4e6, mod = 1000000007;
int add(int x, int y) {return ((x += y) >= mod) ? x-mod : x;}
void addn(int &x, int y) {if((x += y) >= mod) x -= mod;}
int mins(int x, int y) {return ((x -= y) < 0) ? x+mod : x;}
struct G{
struct edge{
int to, nxt, w;
} e[M << 1];
int head[M], cnt1 = 1;
void link(int u, int v) {
e[++cnt1] = {v, head[u], 1}; head[u] = cnt1;
}
}g1, g2;
int fa[M];
int dfn[M], low[M], cnt; bool cut[M];
void tarjan(int u, int f) {
low[u] = dfn[u] = ++cnt;
for(int i = g1.head[u]; i; i = g1.e[i].nxt) {
int v = g1.e[i].to; if(v == f) continue;
if(!dfn[v]){
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]) g1.e[i].w = g1.e[i ^ 1].w = 0; // 0 标记为割边，i^1 用了成对变换的技巧，把反边一起标记
}
else low[u] = min(low[u], dfn[v]);
}
}
int siz1[M], siz2[M]; bool vis[M];
int bl[M];
int n, m, cnt2;
// 用于划分连通块，siz1 对应行文中的 cntp，点数；siz2 对应行文中的 cnte，边数
void dfs2(int u, int f, int t) {
bl[u] = t; vis[u] = 1; ++siz1[t];
for(int i = g1.head[u]; i; i = g1.e[i].nxt) {
if(g1.e[i].w) ++siz2[t];
int v = g1.e[i].to;
if(g1.e[i].w == 0 || v == f) continue;
if(!vis[v]) dfs2(v, u, t);
}
}
int sm[M];
// 用于计算文中的 sum 数组，子树中边数和，包括被缩掉者
void dfs4(int u, int fa) {
sm[u] = siz2[u];
for(int i = g2.head[u]; i; i = g2.e[i].nxt) {
int v = g2.e[i].to; if(v == fa) continue;
dfs4(v, u);
sm[u] += sm[v] + 1;
}
}
int dp[M][2], pw[M], ans;
// 统计答案的 dfs，dp 意义如上文所叙
// dp_{u,0} 强制 u 及其子树不选任意一个点（空）
// dp_{u,1} 强制 u 及其子树选至少一个点，且所有被选的点与 u 连通（不空）。
void dfs3(int u, int fa) {
dp[u][0] = pw[siz2[u]];
dp[u][1] = 1ll * pw[siz2[u]] * (pw[siz1[u]] - 1) % mod;
int tot = 0;
for(int i = g2.head[u]; i; i = g2.e[i].nxt) {
int v = g2.e[i].to; if(v == fa) continue;
dfs3(v, u);
dp[u][1] = add(1ll * dp[u][1] * add(1ll * dp[v][0] * 2 % mod, dp[v][1]) % mod, 1ll * dp[u][0] * dp[v][1] % mod);
dp[u][0] = 1ll * dp[u][0] * 2 % mod * dp[v][0] % mod;
addn(tot, dp[v][1]);
}
if(u != n+1) addn(ans, 1ll * dp[u][1] * pw[sm[n+1] - sm[u] - 1] % mod);
else addn(ans, 1ll * dp[u][1] % mod);
}
int find(int u) {return u == fa[u] ? u : fa[u] = find(fa[u]);}
void merge(int u, int v) {if((u = find(u)) != (v = find(v))) fa[u] = v;}
int main(){
scanf("%d %d", &n, &m);
pw[0] = 1;
for(int i = 1; i <= 2 * n + m; i++) pw[i] = 1ll * pw[i-1] * 2 % mod;
for(int i = 1; i <= m; i++) {
int u, v; scanf("%d %d", &u, &v);
g1.link(u, v); g1.link(v, u);
}
tarjan(1, 0); cnt2 = n;
for(int i = 1; i <= n; i++) if(!vis[i]) dfs2(i, 0, ++cnt2);
for(int i = n+1; i <= 2*n; i++) {
siz2[i] /= 2;
}
// 缩边
for(int i = 1; i <= 2*n; i++) fa[i] = i;
for(int u = 1; u <= n; u++) {
for(int i = g1.head[u]; i; i = g1.e[i].nxt) {
int v = g1.e[i].to;
if(find(bl[u]) != find(bl[v])) g2.link(bl[u], bl[v]), g2.link(bl[v], bl[u]), merge(bl[u], bl[v]);
}
}
// n+1 是缩完边后树的根
dfs4(n+1, 0);
dfs3(n+1, 0);
printf("%d\n", ans);
}
感觉这是一道口嗨很简单的题，但细节什么的确实需要想清楚。评上位蓝或下位紫很恰当。
虽然我的思路看着很杂乱，但这确实是自己一步步想到的思路，自觉每一步的转化都能从上一步找到端倪，因为这是自己真实的思考过程。
赛时一眼缩边+树形 dp，然而没调完，花了 1h 回忆缩边的过程，回家再花了 30min 才写完。得到的教训是要好好复习学过的东西。
完结撒花 ovo
原文地址：http://www.cnblogs.com/purplevine/p/16930223.html
