Nebius Welcome Round : F. Approximate Diameter

変わった出力条件。
https://codeforces.com/contest/1804/problem/F

問題

連結グラフの直径は、2点の最短距離のうちの最大値とする。
辺を1個追加するクエリがQ個与えられるので、その都度その直径を求めたい。
その際、倍・半分まではずれていても良い。

解法

1つ点を定め、そこから最遠点までの距離を求めると、直径の半分以上直径以下になる。

f(n)をn個目までのクエリを処理した場合の上記の値とする。
f(L)とf(R)が倍半分以上差がなければ、L～R個目までのクエリにはf(L)の値を答えておけばよいし、そうでなければf((L+R)/2)を求めて再帰的に処理しよう。

int N,M,Q;
int U[202020],V[202020];
int ret[202020];
int D[202020];
vector<int> E[202020];
int hoge(int v) {
	int i;
	FOR(i,N) {
		E[i].clear();
		D[i]=1LL<<20;
	}
	FOR(i,M+v) {
		E[U[i]].push_back(V[i]);
		E[V[i]].push_back(U[i]);
	}
	D[0]=0;
	queue<int> Q;
	Q.push(0);
	int ma=0;
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		ma=max(ma,D[cur]);
		FORR(e,E[cur]) if(D[e]>1LL<<19) {
			D[e]=D[cur]+1;
			Q.push(e);
		}
	}
	return ma;
}

void dfs(int L,int R) {
	if(L+1>=R) return;
	if(ret[R]*2>=ret[L]) {
		int i;
		for(i=L+1;i<R;i++) ret[i]=ret[L];
		return;
	}
	int M=(L+R)/2;
	ret[M]=hoge(M);
	dfs(L,M);
	dfs(M,R);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,M+Q) {
		cin>>U[i]>>V[i];
		U[i]--;
		V[i]--;
	}
	
	ret[0]=hoge(0);
	ret[Q]=hoge(Q);
	dfs(0,Q);
	
	FOR(i,Q+1) cout<<ret[i]<<" ";
	cout<<endl;
}

まとめ

これ系のクエリ処理、時々出るけどさっと解法にたどり着けないんだよな。