1154: [STT2024JanR2] 不可持久化动态无向图的无源汇全局任意割
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：9
解决：4
题目描述
给定一张无向图 $G=(V,E)$，每条边有一个权值 $w(u,v)$，为割掉它的代价。一个任意割 $C$ 是原图边集 $E$ 的一个非空子集，删去后将生成一张新图 $G'=(V',E')$。定义一个割的代价为割掉边权值 $w(u,v)$ 的总和，即 $\rvert C \lvert=\sum_{(u,v)\in C} w(u,v)$。
你需要支持以下操作：
1. 新增一条边，边权为 $w$，连接结点 $u,v$，保证 $u,v$ 之前没有直接连边；
2. 删除一条连接 $u,v$ 的边，保证这条边存在。
3. 查询整张图有多少种任意割的方案，答案对 $998244353$ 取模。
你需要支持以下操作：
1. 新增一条边，边权为 $w$，连接结点 $u,v$，保证 $u,v$ 之前没有直接连边；
2. 删除一条连接 $u,v$ 的边，保证这条边存在。
3. 查询整张图有多少种任意割的方案，答案对 $998244353$ 取模。
输入
输入的第一行包含三个正整数 $N, M, Q$，表示结点个数，图上已有的边，操作次数。
接下来 $m$ 行每行三个数字，$v_i,u_i$ 表示一条连接 $v_i$ 和 $u_i$，边权为 $w_i$ 的边。
接下来 $Q$ 行，每行第一个数字表示操作类型，若为 $1$ 则接下来会有三个数 $u,v,w$。若为 $2$，接下来会有两个数 $u,v$ 表示删除 $u$ 和 $v$ 之间的连边。若为 $3$ 则表示一次询问。
接下来 $m$ 行每行三个数字，$v_i,u_i$ 表示一条连接 $v_i$ 和 $u_i$，边权为 $w_i$ 的边。
接下来 $Q$ 行，每行第一个数字表示操作类型，若为 $1$ 则接下来会有三个数 $u,v,w$。若为 $2$，接下来会有两个数 $u,v$ 表示删除 $u$ 和 $v$ 之间的连边。若为 $3$ 则表示一次询问。
输出
对于每次询问，输出一行一个值，表示此时整张图任意割的方案数对 $998244353$ 取模的值。
样例输入 复制
4 5 2
1 2 1
2 3 29
3 4 3
4 1 4
2 4 2
2 2 3
3样例输出 复制
15提示
### 样例 #2
#### 样例输入 #2
```
100000 0 1
3
1 2 4 82
3
```
#### 样例输出 #2
```
0
1
```
### 提示
**【样例 #1 解释】**
割掉 $2$，$3$ 之间的连边后，还剩 $1-2$，$2-4$，$1-4$，$3-4$，四条边。
| 割掉边数 | 方案 $1$ |方案 $2$|方案 $3$|方案 $4$|方案 $5$ | 方案 $6$ |
| :-:| :-: | :-: | :-: | :-: | :-: | :-: |
| $1$ | 割掉 $1-2$，代价为 $1$ | 割掉 $2-4$，代价为 $2$ | 割掉 $3-4$，代价为 $3$ | 割掉 $1-4$，代价为 $4$ |||
| $2$ | 割掉 $1-2$ 和 $2-4$，代价为 $3$ | 割掉 $1-2$ 和 $3-4$，代价为 $4$ | 割掉 $1-2$ 和 $1-4$，代价为 $5$ | 割掉 $2-4$ 和 $3-4$，代价为 $5$ | 割掉 $2-4$ 和 $1-4$，代价为 $6$ | 割掉 $3-4$ 和 $1-4$，代价为 $7$ |
| $3$ | 除 $1-4$ 外都割掉，代价为 $6$ | 除 $3-4$ 外都割掉，代价为 $7$ | 除 $2-4$ 外都割掉，代价为 $8$ | 除 $1-2$ 外都割掉，代价为 $9$ |||
| $4$ | 全部割掉，代价为 $10$||||||
共 $15$ 种方案。
**【样例 #2 解释】**
一开始没有边，所以任意割方案为 $0$。
加入 $1-2$ 这条边后，只有割掉 $1-2$ 这种方法，代价为 $82$，所以答案为 $1$。
**【数据范围】**
对于 $40\%$ 的数据，满足 $1 \leq n \leq 20$，$1 \leq m \leq 40$，$1 \leq Q \leq 100$。
对于 $100\%$ 的数据，满足 $1 \leq n \leq 10^5$，$0 \leq m \leq 10^6$，$1 \leq Q \leq 10^6$，$0 \leq w_i \leq 10^9$。
注意：本题输入输出量较大，请使用较快的读写方式。