分数: 475 点
问题陈述
给你一个简单的连通无向图 G 与 N 顶点和 M 边缘。 在这里, N \geq 2。 顶点已编号 1 to N,并且边缘已编号 1 to M;边缘 i 连接顶点 U_i 和 V_i。 每条边都有一个值,称为 成本 二进制字符串的,以及边缘成本 i is 2^i.
现在您将选择 G 删除,使连通分量的数量 G 正好变成 2。 (可以证明,在本问题的约束下,这总是可以实现的。)
求已删除边的最小可能成本总和,模 998244353。 (请注意,您没有最小化余数模 998244353.)
约束
- 2 \leq N \leq 2\times 10^5
- N-1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)
- 1 \leq U_i < V_i \leq N
- (U_i, V_i) \neq (U_j, V_j) if i \neq j
- G 已连接。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
输出
输出已删除边的最小可能成本总和,模 998244353.
示例输入 1
5 7 2 3 1 2 1 5 4 5 2 4 3 5 1 3
示例输出 1
22

删除边 1, 2, 4 (上图中虚线所示的边)使得连通分量的数量 G 正是 2.
在这种情况下,删除的边的成本总和为 2^1+2^2+2^4=22,这是最小值。
示例输入 2
2 1 1 2
示例输出 2
2
示例输入 3
8 16 2 7 5 7 6 8 1 7 4 7 1 3 2 8 5 8 4 8 2 5 3 4 3 8 1 4 1 8 4 6 1 2
示例输出 3
54