前言
在学校机房被学长推荐了这道题，听完正解后惊为天人...
简化版题面
给定一张无向连通图，定义直径 \(d=\max(dis(i,j)) \quad (i,j \in N)\) ，其中 \(dis(i,j)\) 指的是 \((i,j)\) 之间的最短距离。接下来会有 \(q\) 次加边操作，每次操作之间不独立，操作完成后输出当前无向图的直径。
数据范围 \(n,m,q \leq 10^5\)
正解
首先我们发现，求严格直径是不可做的，那么就必须考虑如何利用误差范围去简化问题。
不妨先考虑上界的运用，假设我们已经求出了直径 \(l\) ，端点为 \(S,T\) ，考虑图上任意一个点 \(p\) ，有这样的结论 \(max(dis(p,S),dis(p,T)) \geqslant \frac{l}{2}\)
考虑证明这个结论，因为 \(dis(p,S)+dis(p,T) \leq l\) ，所以二者的最大值至少占一半。
考虑运用这个结论，不妨让 \(p=1\) ,这样问题就转化成了求1到其他点最短路的最大值，这样就可以求出来一条至少大于 \(\frac{l}{2}\) 的路径。
之后我们把求出来的长度乘二，就得出了当前图的合法答案。
那下界怎么使用呢？
我们发现，这道题中只有加边的操作，所以图中直径的长度肯定是单调不上升的。
这样我们就可以求出当前图的合法直径，然后二分一个状态使得那个状态的合法直径是当前合法直径的一半，就说明这两个状态之间的所有状态中一开始的直径都是合法的。
之后我们再去求下一个状态的合法直径，用二分往后跳。
复杂度 \(O((n+m)\log(q))\)
标签：状态,题解,Approximate,合法,CF1804F,直径,考虑,dis From： https://www.cnblogs.com/sky-light/p/17230542.html