题目解析

我们有一个无向连通图 $G_0$，有 $n$ 个点、$m$ 条边（可能有重边、自环，边权为 $1$）。然后依次添加 $q$ 条边，得到 $G_1, G_2, \dots, G_q$。对于每个 $i\ (0\le i\le q)$，需要输出一个正整数 $a_i$，满足：

$$\left\lceil \frac{d(G_i)}{2} \right\rceil \le a_i \le 2\cdot d(G_i) $$

其中 $d(G_i)$ 是图 $G_i$ 的直径。即 $a_i$ 是 $d(G_i)$ 的 两倍近似（误差允许在一倍到两倍之间）。

基本概念

• 距离 $\rho_G(u,v)$：$u$ 和 $v$ 在图 $G$ 中的最短路径长度（边数）。
• 离心率 $c_G(u)=\max_{v\in V} \rho_G(u,v)$：从 $u$ 出发到最远点的距离。
• 直径 $d(G)=\max_{u\in V} c_G(u)$：图中任意两点间最大距离。
• 半径 $r(G)=\min_{u\in V} c_G(u)$：最小的离心率。

核心不等式

对于任意图 $G$ 和任意顶点 $v$，有：

$$\frac{d(G)}{2} \le r(G) \le c_G(v) \le d(G) \le 2r(G) \le 2c_G(v) \le 2d(G). $$

证明：

• $r(G)\le c_G(v)\le d(G)$ 由定义直接得到。
• $d(G)\le 2r(G)$：设 $x$ 是达到半径的顶点（即 $c_G(x)=r(G)$），$u,w$ 是直径的端点。由三角不等式：$$d(G)=\rho(u,w) \le \rho(u,x)+\rho(x,w) \le c_G(x)+c_G(x)=2r(G). $$

因此，任意一个顶点的离心率 $c_G(v)$ 已经是直径的一个两倍近似，因为：

$$\frac{d(G)}{2} \le r(G) \le c_G(v) \le d(G) \le 2c_G(v). $$

所以如果我们能快速求出某个固定顶点（比如 $1$）在每个图 $G_i$ 中的离心率 $c_{G_i}(1)$，直接输出它就满足要求。

朴素做法

对于每个 $G_i$，运行一次 BFS 从顶点 $1$ 开始，得到最远距离 $c_{G_i}(1)$，复杂度 $O(q\cdot (n+m+q))$，不可接受（$n,m,q$ 最大 $10^5$）。

关键观察

1. 直径单调不增：加边不会让任何距离变大，所以 $d(G_0)\ge d(G_1)\ge \dots \ge d(G_q)$。
2. 离心率单调不增：同样 $c_{G_0}(1)\ge c_{G_1}(1)\ge \dots \ge c_{G_q}(1)$。

利用单调性的优化

如果我们已经知道 $c_{G_i}(1)$，并且找到某个 $j\ge i$ 使得 $c_{G_i}(1)\le 2c_{G_j}(1)$，那么对于所有 $t\in[i,j]$，$c_{G_i}(1)$ 都是 $d(G_t)$ 的有效近似。

验证：对于 $t\in[i,j]$，$d(G_t)\ge d(G_j)\ge \frac{c_{G_j}(1)}{2}$（因为 $c_{G_j}(1)\le d(G_j)$ 但我们需要下界？实际上 $d(G_j)\ge c_{G_j}(1)/2$ 不一定成立，因为 $c_{G_j}(1)$ 可能很小而直径很大。但我们需要的是 $c_{G_i}(1)\ge \lceil d(G_t)/2\rceil$。由 $t\le i$ 时 $d(G_t)\ge d(G_i)$，且 $c_{G_i}(1)\ge d(G_i)/2$，所以 $c_{G_i}(1)\ge d(G_t)/2$。当 $t>i$ 时 $d(G_t)\le d(G_i)$，所以 $c_{G_i}(1)\ge d(G_i)/2 \ge d(G_t)/2$。因此下界满足。上界：$c_{G_i}(1)\le 2d(G_t)$ 是否成立？需要 $c_{G_i}(1)\le 2d(G_j)$，因为 $d(G_t)\ge d(G_j)$，所以 $2d(G_t)\ge 2d(G_j)$。而 $c_{G_i}(1)\le 2c_{G_j}(1)\le 2d(G_j)\le 2d(G_t)$。因此成立。所以 $c_{G_i}(1)$ 在整个区间 $[i,j]$ 都是合法近似。

于是我们可以：

• 维护当前左指针 $L=0$。
• 用 BFS 计算 $c_{G_L}(1)$。
• 二分查找最大的 $R\ge L$ 使得 $c_{G_L}(1)\le 2c_{G_R}(1)$（注意 $c_{G_R}(1)$ 需要提前知道，可以通过 BFS 计算或预处理）。
• 对于 $t=L..R$ 输出 $c_{G_L}(1)$。
• 令 $L=R+1$ 重复。

这样每次二分需要 $O(\log q)$ 次 BFS，总 BFS 次数 $O(q\log q)$，仍然过大。

更高效的分治方法

核心思想：如果 $c_{G_l}(1)\le 2c_{G_r}(1)$，那么整个区间 $[l,r]$ 都可以用 $c_{G_l}(1)$ 一次覆盖。否则，直径下降很快（至少减半），在中间分治。

定义递归函数 solve(l, r, cl, cr)，其中 cl = c_{G_l}(1)，cr = c_{G_r}(1) 已经计算好。

def solve(l, r, cl, cr):
    if l == r:
        输出 cl
        return
    if cl <= 2 * cr:
        for t in [l..r]: 输出 cl
    else:
        mid = (l + r) // 2
        cm = bfs(mid)   # 计算 c_{G_mid}(1)
        solve(l, mid, cl, cm)
        solve(mid+1, r, cm, cr)

复杂度分析：

• 每次进入 else 分支，意味着 $c_l > 2c_r$，由 $c_l\le d(G_l)$ 和 $c_r\ge d(G_r)/2$ 可得 $d(G_r) < d(G_l)$，且实际上直径至少减半。
• 直径最大为 $n$，所以递归深度为 $O(\log n)$。
• 在每一层，每个区间最多被分裂一次，因此总的 BFS 调用次数为 $O(\log n \cdot \log q)$。具体来说，递归树类似于线段树，但只有那些满足 $c_l > 2c_r$ 的节点才会继续分裂，而这样的节点在每层数量有限，且总深度为 $\log n$，所以节点总数为 $O(\log n \cdot \log q)$。
• 每次 BFS 复杂度 $O(n+m+q)$，总复杂度 $O(\log n \cdot \log q \cdot (n+m+q))$。

实现细节

1. 固定源点 $v=1$。
2. 由于 $n,m,q\le 10^5$，一次 BFS 扫描所有边 $O(n+m+q)$ 是可行的。总 BFS 次数约 $\log n \cdot \log q \approx 17 \times 17 = 289$，总操作约 $289 \times 2\times 10^5 = 5.78\times 10^7$，可接受。
3. 每次 BFS 需要重建图。我们可以预先存储所有边（初始 $m$ 条 + 更新 $q$ 条），在 bfs(t) 中只使用前 $m+t$ 条边。
4. BFS 过程：邻接表动态构建，从顶点 $1$ 开始，队列维护，记录最大距离。

正确性证明

• 当 $c_l \le 2c_r$ 时，对于任意 $t\in[l,r]$，有 $c_l \ge d(G_t)/2$（因为 $d(G_t) \le d(G_l) \le 2c_l$ ？需要仔细：$d(G_l)\le 2c_l$ 由不等式，且 $d(G_t)\le d(G_l)$，所以 $d(G_t)/2 \le c_l$。同时 $c_l \le 2c_r \le 2d(G_r) \le 2d(G_t)$。因此 $c_l$ 是 $d(G_t)$ 的有效近似。
• 在递归过程中，每个区间都会被某个“祖先”区间覆盖，最终每个时刻 $t$ 都会被输出某个 $c_{G_{l_t}}(1)$，且 $l_t\le t$，满足上述条件。

扩展思考

Bonus 问题：猜猜他们用了多少 CPU 天来计算所有测试点的精确直径？留给大家在评论区讨论。