题目

给定一个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];
vector
e[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<