唉确实没见过这种二分形式。
https://codeforces.com/problemset/problem/1804/F
注意到这个范围基本上就是 图直径的这个性质，但是我不认识 😅
每次修改做一次 BFS 过于抽象，发现这个上界多了个 \(2\) 的系数，把主元换成 \(d\) 可以得到 \(d\in[0.5s,2s]\)。有一个很牛的操作，假设在当前图上求出来了一个 \(s'\)，显然一直加边，\(2s\) 这个上界是在变小的，但只要 \(s'\le 2s\) 成立，\(s'\) 就一直可以作为区间里的一个估值。如果不成立，发现除以二就成立了。
转化成二分 \(s'\) 最远可以达到的距离即可。每次 \(s'\) 除以二，共除了 \(\log n\) 次；复杂度 \(O(n\log^2 n)\)。
然后注意不要每次 check 都复制一遍原数组然后加边；应该预先在原图上加好所有边，记录版本。原因是申请空间特别费时间。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m, q;
std::cin >> n >> m >> q;
std::vector<std::vector<std::pair<int, int> > > g(n + 1);
for (int x, y; m--; ) {
std::cin >> x >> y;
g[x].emplace_back(y, 0), g[y].emplace_back(x, 0);
}
for (int i = 1, x, y; i <= q; ++i) {
std::cin >> x >> y;
g[x].emplace_back(y, i), g[y].emplace_back(x, i);
}
std::vector<int> mem(q + 1, -1);
auto calc = [&](int id) {
if (~mem[id])
return mem[id];
std::queue<std::pair<int, int> > q;
std::vector<int> tag(n + 1);
q.emplace(1, 0), tag[1] = 1;
int mx = 0;
for (; !q.empty(); ) {
auto [x, w] = q.front();
q.pop(), mx = w;
for (auto [i, ver] : g[x])
if (ver <= id && !tag[i]) {
tag[i] = 1;
q.emplace(i, w + 1);
}
}
return mem[id] = mx;
};
int s = calc(0);
for (int i = 0; i <= q; ) {
int j = i;
for (int l = i + 1, r = q, mid; l <= r; ) {
mid = (l + r) >> 1;
if (s <= 2 * calc(mid))
j = mid, l = mid + 1;
else
r = mid - 1;
}
for (; i <= j; ++i)
std::cout << s << ' ';
s /= 2;
}
std::cout << '\n';
return 0;
}