题目链接
题目解法
很有意思的题，但不难
首先一个显然的结论是：算着边的加入，直径长度递减
第一眼看到误差范围是 2 倍，可以想到二分
可以观察到如果取答案为 \(\frac{n}{2}\) 可以覆盖到 \(\frac{n}{4}\)（上下取整不重要），那这样每次可以把值域范围缩小 4 倍，然后只要二分直径在这个范围内的操作区间即可
但现在有问题是无法求出一个图的直径
继续考虑估测
有一个结论是：图上任意一点到其他点的最远距离 \(\ge \frac{diameter}{2}\)
这不难证明，具体来说，在直径上的点显然是满足结论的，不在直径上的点需要先到直径上，才能到端点，显然也是满足结论的
然后就稍微变化一下上面的二分区间就可以做到 \(O(n\log^2n)\) 的复杂度
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=100100,M=100100;
int n,m,q,ans[M],dis[N];
pii E[M<<1];
queue<int> que;
vector<int> G[N];
void add_edge(int x,int y){ G[x].pb(y),G[y].pb(x);}
int get_dia(int opt){
F(i,1,n) G[i].clear(),dis[i]=-1;
F(i,1,m) add_edge(E[i].x,E[i].y);
F(i,1,opt) add_edge(E[i+m].x,E[i+m].y);
que.push(1),dis[1]=0;
while(!que.empty()){
int u=que.front();que.pop();
for(int v:G[u]) if(dis[v]==-1) dis[v]=dis[u]+1,que.push(v);
}
int ret=0;
F(i,1,n) chkmax(ret,dis[i]);return ret;
}
int main(){
n=read(),m=read(),q=read();
F(i,1,m) E[i]={read(),read()};
F(i,1,q) E[i+m]={read(),read()};
int x=get_dia(0),L=0;
while(true){
int lo=L-1,hi=q+1;
while(lo<hi-1){
int mid=(lo+hi)/2,dia=get_dia(mid);
if(dia>=(x+1)/2) lo=mid;
else hi=mid;
}
F(i,L,lo) ans[i]=x;
L=lo+1;
if(!x) break;
x/=2;
}
F(i,0,q) printf("%d ",ans[i]);puts("");
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}