题解说明

问题背景：
给定一个无向图，要求计算与图的点双连通分量（BCC）相关的某种组合计数。代码通过 Tarjan 算法求点双，构建缩点树，再在缩点树上做树形 DP，最后结合边数修正得到答案。

核心思路：
$1.$ Tarjan 算法求点双：

• 使用 $dfn[u]$ 和 $low[u]$ 数组，结合栈 $S$，找到所有点双连通分量。
• 每个点双分配一个编号 $id[u]$，并统计其包含的原图节点数 $a[id]$。

$2.$ 缩点树构建：

将每个点双看作一个新节点。

原图中跨点双的边在缩点树中连边。

• 同一个点双内部的边单独计数，记为 $cnt$。

$3.$ 树形 DP 计算贡献：

• 在缩点树上 DFS。

定义：

• $sz[u]$：以 $u$ 为根的子树包含的点双数
• $f[u]$：子树 $u$ 的贡献值

转移：
$f[u]$ 初始为 $2^{a[u]}$。
遍历子树 $v$，更新 $f[u] = f[u] \times (2^{sz[v]} + f[v])$。
最后减去重复计数的部分，得到净贡献 $s$。

• 将 $s$ 乘上 $2^{tot - sz[u]}$，累积到全局答案 $ans$。

$4.$ 最终修正：

• 因为同一个点双内部的边在输入时存了两次，所以 $cnt$ 实际为 $2 \times \text{边数}$。
• 最终答案需乘上 $2^{cnt/2}$。

算法流程：
$1.$ 输入 $n,m$，读入边，建原图 $G_1$。
$2.$ 预处理 $2$ 的幂数组 $Pow$。
$3.$ 对每个未访问节点运行 Tarjan，得到所有点双。
$4.$ 遍历原图节点，统计每个点双的节点数，并构建缩点树 $G_2$。
$5.$ 在缩点树上 DFS，计算贡献并累积到 $ans$。
$6.$ 最终答案乘上 $2^{cnt/2}$，输出。

复杂度分析：

• Tarjan 算法：$O(n+m)$

构建缩点树：$O(n+m)$

• 树形 DP：$O(n)$
• 总复杂度：$O(n+m)$，适合 $n \leq 5 \times 10^5,\ m \leq 10^6$ 的数据范围。

实现细节与注意点：

• Tarjan 中避免回退父边：通过 $(i \oplus fa \oplus 1)$ 判断。
• $Pow$ 数组需预处理到 $\max(n,m)$。
• 缩点树是无根树，任选 $1$ 号点双为根 DFS。
• 答案取模 $10^9+7$。
• $cnt$ 统计时注意每条边存了两次，最终需除以 $2$。

总结：
该算法通过“Tarjan 求点双 $+$ 缩点树 $+$ 树形 DP”的组合，成功将原图的复杂结构转化为树结构上的 DP 计算，保证了线性复杂度，能够在大规模数据下高效求解。

#include <cstdio>
#include <stack>
#include <algorithm>  // 原代码依赖std::min，补充头文件
#define re register  // 宏定义：寄存器变量修饰符，提升循环效率
#define gc getchar   // 宏定义：简化标准输入字符读取函数
#define il inline    // 宏定义：inline修饰符，建议编译器内联函数
#define vd void      // 宏定义：简化void类型书写
#define ret return   // 宏定义：简化return关键字书写
#define ll long long // 宏定义：简化long long类型书写

// 快速读入整数：避免cin/scanf的性能损耗，适用于大数据输入
il int rd() {
    re int x = 0;          // 存储读取的整数结果
    re char xr = gc();     // 读取第一个字符（跳过非数字）

    // 跳过所有非数字字符（如空格、换行、字母）
    for (; '0' > xr || xr > '9'; xr = gc());

    // 读取连续数字字符，转换为整数（(x<<3)+(x<<1) = x*8 + x*2 = x*10）
    for (; '0' <= xr && xr <= '9'; 
         x = (x << 3) + (x << 1) + (xr ^ 48),  // xr^48 等价于 xr-'0'（ASCII码转换）
         xr = gc());

    ret x;  // 返回读取的整数
}

// 全局常量定义
const int N = 5e5 + 3;    // 原图最大节点数
const int M = 1e6 + 3;    // 原图最大边数
const int p = 1e9 + 7;    // 模数：用于计算2的幂和答案取模

// 全局变量定义
int n, m;                 // n：原图节点数；m：原图边数
int ind;                  // DFN序计数器：记录节点被访问的时间戳
int low[N];               // Tarjan算法用：节点u能到达的最早DFN序节点
int dfn[N];               // Tarjan算法用：节点u的访问时间戳（DFN序）
int tot;                  // 点双连通分量（BCC）总数：缩点后的节点数
int id[N];                // 原图节点→点双编号的映射：id[u]表示u属于第几个点双
int a[N];                 // 每个点双的节点数：a[bcc_id] = 该点双包含的原图节点数
int cnt;                  // 统计原图中“属于同一个点双”的边数（用于最终答案计算）
int sz[N];                // 缩点树的子树大小：sz[u]表示u为根的子树包含的点双个数
ll Pow[M];                // 预处理2的幂：Pow[i] = 2^i mod p
ll f[N];                  // 树形DP数组：f[u]表示u点双在子树内的贡献值
ll ans;                   // 最终答案：累积所有点双的贡献

// 图结构体：存储邻接表（支持加边操作）
struct Graph {
    int ind = 1;          // 边计数器：从1开始（避免0号边，方便处理无向边）
    int hd[N];            // 邻接表头指针：hd[u]表示u的第一条边的索引
    int to[M << 1];       // 边的目标节点：to[i]表示第i条边指向的节点
    int nxt[M << 1];      // 边的下一条指针：nxt[i]表示第i条边的下一条边索引

    // 加边函数：给无向图添加u→v的边（实际存双向边，调用时需加两次）
    il vd add(int u, int v) {
        ++ind;            // 边计数器自增
        to[ind] = v;      // 记录当前边的目标节点
        nxt[ind] = hd[u]; // 当前边的下一条边指向u的原表头
        hd[u] = ind;      // 更新u的表头为当前边
        ret;              // 函数返回（vd类型无返回值）
    }
} G_1, G_2;  // G_1：原图（存储原始无向边）；G_2：缩点树（点双为节点，存储点双间的连接）

std::stack<int> S;  // Tarjan算法用栈：存储待确定点双的节点

// Tarjan算法：求原图的点双连通分量（BCC）
// u：当前处理的节点；fa：当前节点的父边索引（避免回退到父节点）
vd Tarjan(int u, int fa) {
    low[u] = dfn[u] = ++ind;  // 初始化当前节点的DFN序和low值（时间戳自增）
    S.push(u);                // 将当前节点压入栈，标记为待处理

    // 遍历当前节点u的所有邻边
    for (re int i = G_1.hd[u], v; v = G_1.to[i]; i = G_1.nxt[i]) {
        if (!dfn[v]) {  // 邻节点v未访问：递归处理v
            Tarjan(v, i);  // 传入当前边i作为v的父边
            low[u] = std::min(low[u], low[v]);  // 用v的low值更新u的low值
        } else if ((i ^ fa ^ 1) != 0) {  // 邻节点v已访问，且边i不是父边（无向边需跳过父边）
            // i^fa^1：无向边存储为双向（如i和i^1），判断是否为父边的反向边
            low[u] = std::min(low[u], dfn[v]);  // 用v的DFN序更新u的low值
        }
    }

    // 满足点双条件：当前节点u是点双的根（low[u] == dfn[u]）
    if (low[u] == dfn[u]) {
        ++tot;  // 点双计数器自增（新点双编号）
        // 弹出栈中节点，直到当前节点u（这些节点构成一个点双）
        for (;;) {
            id[S.top()] = tot;  // 标记栈顶节点属于当前点双tot
            if (S.top() == u) { // 栈顶是当前节点u：点双收集完成
                S.pop();        // 弹出u
                break;          // 退出循环
            }
            S.pop();            // 弹出栈顶节点（属于当前点双）
        }
    }
    ret;
}

// 树形DP：在缩点树G_2上计算每个点双的贡献，累积到ans
// u：当前处理的缩点树节点（点双编号）；fa：当前节点的父节点（避免回退）
vd dfs(int u, int fa) {
    sz[u] = 1;                // 初始化子树大小：当前点双本身（1个节点）
    f[u] = Pow[a[u]];         // 初始化f[u]：2^(当前点双的节点数) mod p（基础贡献）

    // 遍历缩点树中u的所有邻节点（子节点）
    for (re int i = G_2.hd[u], v; v = G_2.to[i]; i = G_2.nxt[i]) {
        if (v == fa) continue; // 跳过父节点，避免循环

        dfs(v, u);             // 递归处理子节点v
        // 更新f[u]：子树v的贡献 = (2^sz[v] + f[v])，乘到f[u]中（取模）
        // 2^sz[v]：子树v不选当前点双的情况；f[v]：子树v选当前点双的情况
        f[u] = f[u] * (Pow[sz[v]] + f[v]) % p;
        sz[u] += sz[v];        // 更新子树大小：加入子树v的大小
    }

    // 调整f[u]：减去“只选当前点双单个节点”的情况（避免重复计算）
    f[u] = (f[u] - Pow[sz[u] - 1] + p) % p;
    re ll s = f[u];            // s：当前点双u的净贡献（初始为f[u]）

    // 减去子树v的独立贡献（避免重复累积子树贡献）
    for (re int i = G_2.hd[u], v; v = G_2.to[i]; i = G_2.nxt[i]) {
        if (v == fa) continue; // 跳过父节点
        // 子树v的独立贡献 = f[v] * 2^(sz[u]-sz[v]-1) mod p
        s = (s - f[v] * Pow[sz[u] - sz[v] - 1] % p + p) % p;
    }

    // 累积当前点双u的总贡献：s * 2^(tot - sz[u]) mod p
    // 2^(tot - sz[u])：非u子树的点双的贡献（每个可选或不选）
    ans = (ans + 1ll * s * Pow[tot - sz[u]] % p) % p;
    ret;
}

signed main() {
    // 移除文件读写：原freopen("barrack.in", "r", stdin); freopen("barrack.out", "w", stdout);
    
    n = rd(), m = rd();        // 读取原图节点数n和边数m
    Pow[0] = 1;                // 初始化2^0 = 1（模p）

    // 预处理2的幂：Pow[i] = 2^i mod p（最大到max(n,m)，满足后续计算需求）
    for (re int i = 1; i <= std::max(n, m); ++i) {
        Pow[i] = (Pow[i - 1] << 1) % p;  // 左移1位等价于乘2，取模避免溢出
    }

    // 读取原图m条无向边，构建G_1（每条边存双向）
    for (re int u, v; m--;) {
        u = rd(), v = rd();
        G_1.add(u, v);  // 加u→v的边
        G_1.add(v, u);  // 加v→u的边（无向边双向存储）
    }

    // 对原图每个未访问的节点调用Tarjan，求所有点双连通分量
    for (re int i = 1; i <= n; ++i) {
        if (!dfn[i]) {  // 节点i未分配DFN序（未访问）
            Tarjan(i, 0);  // 父边设为0（无父节点）
            // 7：无实际意义，仅为语法占位（避免空语句警告）
        }
    }

    // 1. 统计每个点双的节点数a[bcc_id]；2. 构建缩点树G_2
    for (re int u = 1; u <= n; ++u) {
        ++a[id[u]];  // 给u所属的点双id[u]的节点数+1

        // 遍历原图u的所有邻边，判断是否跨点双（构建缩点树边）
        for (re int i = G_1.hd[u], v; v = G_1.to[i]; i = G_1.nxt[i]) {
            if (id[u] != id[v]) {  // u和v属于不同点双：跨点双边
                G_2.add(id[u], id[v]);  // 缩点树中加id[u]→id[v]的边
                // 7：语法占位，无实际意义
            } else {
                ++cnt;  // u和v属于同一点双：统计这类边的数量
            }
        }
    }

    // 执行树形DP：从缩点树的1号节点（任意根，树无固定根）开始，计算贡献
    dfs(1, 0);
    // 最终答案调整：乘2^(cnt/2) mod p（cnt是同点双边数，除以2是因为每条边存了两次）
    ans = 1ll * ans % p * Pow[cnt >> 1] % p;
    // 输出最终答案（标准输出到控制台）
    printf("%lld", ans);
    ret 0;
}