P14164 [ICPC 2022 Nanjing R] 命题作文

有一张由 $n$ 个点与 $(n-1)$ 条边构成的无向连通图 $G$。顶点编号从 $1$ 到 $n$（含两端），第 $i$ 条边连接顶点 $i$ 与 $(i + 1)$。 接下来向图中依次加入额外 $m$ 条边（加入后不删除）。每次加入一条额外边后，求从图中选择两条边 $e$ 与 $f$ 的方案数，满足如果边 $e$ 与 $f$ 同时被删除，图将变得不连通（即图中至少有两个连通块）。 请注意，先选择 $e$ 再选择 $f$，和先选择 $f$ 再选择 $e$ 被认为是同一种方案。

有多组测试数据。第一行输入一个整数 $T$ 表示数据组数，对于每组测试数据： 第一行输入两个整数 $n$ 和 $m$（$1 \le n, m \le 2.5\times 10^5$）表示图的点数及增加的额外边数。 对于接下来 $m$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$）表示第 $i$ 条额外边连接顶点 $u_i$ 与 $v_i$。 保证所有数据中 $n$ 之和与 $m$ 之和均不超过 $2.5 \times 10^5$。

每组数据输出 $m$ 行，第 $i$ 行输出一个整数表示加入第 $i$ 条额外边后的答案。

以下对第一组样例数据进行解释。 加入第一条额外边后，任意删除两条边都能将图变得不连通。因此答案为 $6$。 加入第二条额外边后，可以同时选择原始边 $1$ 与任意另一条边，也可以同时选择原始边 $2$ 与原始边 $3$。答案为 $4 + 1 = 5$。 加入第三条额外边后，可以同时选择原始边 $1$ 与任意另一条边，也可以同时选择原始边 $2$ 与原始边 $3$。答案为 $5 + 1 = 6$。