1
注意到权值是 2^i, 容易想到 从1到i-1条边的权值加起来都没有第i条边的一个权值高这个二进制的性质, 于是我们采用"正难则反"的思路解决问题:要求最小删除的边的权值和,即保留最大的边权值和。
2
题目的要求是缩边, 根据正难则反的思路, 我们考虑增边。即假设一开始的点都是相互之间孤立的, 我们不断将孤立的点连接起来，组成一个个连通块，当连通块数量达到2时，就可以停止，以计算需要删除的边的权值
3
我们仿照"最小生成树"的思路, 实现"最大生成树", 并使用并查集进行判断是否在同一个连通块中, 具体逻辑请见代码及其注释

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N=2e5+10;
4
typedef long long ll;
5
const ll mod=998244353ll; //取模的值
6
int n, m;
7
vector<pair<int, int>> g;//存边的两点的vector
8
int fa[N];//并查集所需数组
9
ll res;
10
int find(int x){//路径压缩+查询
11
    if(x!=fa[x]) return fa[x]=find(fa[x]);
12
    return x;
13
}
14

15
int main(){
16
    scanf("%d%d", &n, &m);
17
    int cnt=n;//一开始连通块数量为n
18
    for(int i=0;i<m;i++) {
19
        int u, v;
20
        scanf("%d%d", &u, &v);
21
        g.push_back({u, v});
22
    }
23
    for(int i=1;i<=n;i++) fa[i]=i;//初始化并查集信息
24
    for(int i=m-1;i>=0;i--){//倒序, 从最大的开始
25
        if(cnt==2) break;//只剩两个了, 就可以停止, 因为再合并下去就不满足两个联通分量的要求了. 剩下的边要不属于连通分量1, 要不属于连通分量2, 要不是横跨两个连通分量
26
        int u=g[i].first, v=g[i].second;
27
        u=find(u), v=find(v);
28
        if(u==v) continue;
29
        fa[u]=v;//合并
30
        cnt--; //连通块数量-1
31
    }
32
    ll p=1;
33
    for(int i=0;i<m;i++){
34
        p=p*2%mod;//p就是每个边的权值%mod
35
        int u=g[i].first, v=g[i].second;
36
        if(find(u)==find(v)) continue;//是同一个连通分量里的(要不是1, 要不是2)
37
        res=(res+p)%mod;//这个是横跨了两个分量的, 一定要删掉
38
    }
39
    printf("%lld\n", res);
40
    return 0;
41
}