CF1804F Approximate Diameter

Jack 有一个包含 $n$ 个顶点和 $m$ 条边的图。所有边都是双向且长度为 $1$。该图是连通的，即任意两点之间都存在一条路径。允许有多条边连接同一对顶点，图中也可以存在自环（即一条边连接某个顶点自身）。 顶点 $u$ 和 $v$ 之间的距离记作 $\rho(u, v)$，等于 $u$ 到 $v$ 的最短路径上的边数。图 $G$ 的直径定义为所有顶点对之间距离的最大值，记作 $d(G)$。换句话说，$d(G) = \max_{1 \le u, v \le n}{\rho(u, v)}$。 Jack 计划对他的图连续进行 $q$ 次操作，每次操作向图中添加一条边。记 $G_i$ 为进行了恰好 $i$ 次操作后的图。Jack 想要计算 $q+1$ 个值 $d(G_0), d(G_1), d(G_2), \ldots, d(G_q)$。不过，Jack 认为精确求出这 $q+1$ 个图的直径可能很难，因此他只需要一个与真实答案相差不超过两倍的近似值。形式化地说，Jack 需要找到一个正整数序列 $a_0, a_1, a_2, \ldots, a_q$，使得对于每个 $i$，都有 $\left\lceil \frac{d(G_i)}{2} \right\rceil \le a_i \le 2 \cdot d(G_i)$。

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$2 \leq n \leq 10^5$，$n-1 \leq m \leq 10^5$，$0 \leq q \leq 10^5$），分别表示图中的顶点数、初始边数和操作次数。 接下来 $m$ 行，每行两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示第 $i$ 条初始边连接的两个顶点。 接下来 $q$ 行，每行两个整数 $u'_i$ 和 $v'_i$（$1 \leq u'_i, v'_i \leq n$），表示第 $i$ 次操作添加的边连接的两个顶点。 重要说明：为测试目的，输入数据在上述格式之后可能还包含一些额外的行。这些行将由评测器用于验证你的答案。它们不是测试数据的一部分，你不应使用这些数据，甚至可以忽略读取它们。

输出 $q+1$ 个正整数 $a_0, a_1, a_2, \ldots, a_q$，第 $i$ 个整数应与图 $G_i$ 的直径相差不超过两倍。

在第一个样例中，正确的 $d(G_0), d(G_1), d(G_2), \ldots, d(G_q)$ 序列为 $6, 6, 6, 3, 3, 3, 2, 2, 2$。 在第二个样例中，输入包含一行额外数据，你可以忽略读取。这不是测试数据的一部分，将用于验证你的答案。第二个样例的输出包含了 $d(G_i)$ 的正确值。 由 ChatGPT 4.1 翻译