Nebius Welcome Round (Div. 1 + Div. 2) F. Approximate Diameter(构造/图论性质+二分+最短路)
题目
给定一个n(2<=n<=1e5)个点，m(n-1<=m<=1e5)条边的无向无环图
可能有自环和重边，q(0<=q<=1e5)次加边操作，每次加u和v
要求输出q+1行，即没加边时，和每次加边之后图的直径d(G)
d(G)被定义为图上点u和v之间d(u,v)的最大值，其中d(u,v)是u到v的最短路
注意：
若实际第i(0<=i<=q)次加边后，图的直径为，
而你输出的值为，只要
，即视为正确
思路来源
官方题解 & jly代码
题解
强烈建议知乎问题《有哪些注意不到就做不出来的题》收列此题
翻译一遍题解
计为u到u的图上最远点v的距离，
为
最小值，图的半径；
为
最大值，图的直径
由定义，有，
由三角形不等式，有
证明：
设u、v点构成图的直径d(G)，
不失一般性，设r(G)的某个端点是1号点，另一端点是w点
因为，图的直径不支持两遍bfs，
所以，1号点bfs一次的w点，不一定是u点和v点中的一个，不能用树上的做法放缩，
但是，最远距离是满足放缩条件的，故不等式成立
有
之间的值均符合题意，
可以任取一个点u跑一次bfs，即可实现
优化
注意到，随着动态加边，直径d(G)和每个点u对应的，是非严格递减的，
即
若成立，就有
而符合第i次询问的答案，
符合第j次询问的答案
区间是随着答案非严格递减平移的，
所以，二者区间之交一定满足[i,j]内所有询问的答案
对于当前i，二分满足的最右端点j即可
由于值域，端点
，
复杂度
本题不支持hack，因为官方数据的答案是用分布式跑出来的，有的数据还缀在输入数据尾了
代码
#include
using namespace std;
typedef long long ll;
typedef pair P;
const int N=1e5+10,INF=0x3f3f3f3f;
int n,m,q,dis[N],ans[N];
vectore[N];
int bfs(int t){queueq;q.push(1);memset(dis,INF,sizeof dis);dis[1]=0;while(!q.empty()){int u=q.front();q.pop();for(auto &[v,w]:e[u]){if(w<=t && dis[v]>dis[u]+1){dis[v]=dis[u]+1;q.push(v);}}}return *max_element(dis+1,dis+n+1);
}
int main(){cin>>n>>m>>q;for(int i=1;i<=m;++i){int u,v;cin>>u>>v;e[u].push_back(P(v,0));e[v].push_back(P(u,0));}for(int i=1;i<=q;++i){int u,v;cin>>u>>v;e[u].push_back(P(v,i));e[v].push_back(P(u,i));}for(int i=0;i<=q;){int d=bfs(i);int l=i+1,r=q;while(l<=r){int mid=(l+r)/2;if(d<=2*bfs(mid))l=mid+1;else r=mid-1;}while(i<=r)ans[i++]=d;}for(int i=0;i<=q;++i){cout<