[CF1804F] Approximate Diameter 题解

题目链接

题目分析

显然图结构不太好维护，容易想到维护树结构。维护生成树看起来就不太靠谱，容易想到维护最短路树。

key observation：我们固定一个端点（不妨为 \(1\)），求出这个点到每个点的最短路长度的最大值 \(x\)。则一定有 \(\lceil{d\over 2}\rceil\le x\le d\)。

证明：显然 \(x \le d\)。设直径为 \(u \rightsquigarrow v\)，考虑 \(1 \rightsquigarrow u\) 和 \(1 \rightsquigarrow v\) 两条最短路，根据三角形不等式，这两条最短路的长度之和一定不小于 \(d\)，因此其中较大者一定至少为 \(\lceil{d\over 2}\rceil\)。

考虑动态维护以 \(1\) 为根的最短路树，发现至少需要一棵 LCT。有没有更简单的方法呢？发现我们还没有用到 \(x\) 可以大于 \(d\)（只要不超过 \(2d\)）这一性质。容易发现答案是单调不增的，因此答案减半的次数不超过 \(\log n + O(1)\)，每次二分搜索求出第一次折半的位置即可。求最短路可以使用 BFS。时间复杂度 \(O(n \log^2 n)\)。

代码实现

#include <bits/stdc++.h>

#define FOR(i, l, r) for (int i = l; i < (r); ++i)
#define F0R(i, r) FOR (i, 0, r)
#define ROF(i, l, r) for (int i = r; i-- > (l);)
#define R0F(i, r) ROF (i, 0, r)
#define rep(n) F0R (_, n)
#define each(i, x) for (auto& i : x)

using namespace std;

using ll = long long;
using db = long double;
using str = string;

using pi = pair<int, int>;
#define mp make_pair
#define f first
#define s second

#define ttt template <typename T
ttt > using vec = vector<T>;
ttt, size_t n > using arr = array<T, n>;
using vi = vec<int>;
using vb = vec<bool>;
using vl = vec<ll>;
using vpi = vec<pi>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define rsz resize
#define pb push_back
#define eb emplace_back

#define il inline
ttt > il bool ckmin(T& x, const T& y) { return y < x ? x = y, true : false; }
ttt > il bool ckmax(T& x, const T& y) { return x < y ? x = y, true : false; }

ttt > il T safe_mid(T l, T r) { return (l & r) + ((l ^ r) >> 1); }
ttt, typename F > T find_fst(T l, T r, F f) {
  if (l > r || !f(r)) return r + 1;
  while (l < r) {
    T mid = safe_mid(l, r);
    f(mid) ? r = mid : l = mid + 1;
  }
  return l;
}
ttt, typename F > T find_lst(T l, T r, F f) {
  if (l > r || !f(l)) return l - 1;
  while (l < r) {
    T mid = safe_mid(l, r + 1);
    f(mid) ? l = mid : r = mid - 1;
  }
  return l;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false), cin.exceptions(cin.failbit);

  int n, m, q;
  cin >> n >> m >> q;

  vec<vpi> adj(n);
  rep (m) {
    int u, v;
    cin >> u >> v, --u, --v;
    adj[u].eb(v, -1), adj[v].eb(u, -1);
  }
  F0R (i, q) {
    int u, v;
    cin >> u >> v, --u, --v;
    adj[u].eb(v, i), adj[v].eb(u, i);
  }

  vi dis(n);
  auto bfs = [&](int mid) {
    int ans = 0;
    fill(all(dis), -1), dis[0] = 0;
    queue<int> q{{0}};
    while (!q.empty()) {
      int u = q.front();
      q.pop(), ans = dis[u];
      for (auto [v, w] : adj[u])
        if (w <= mid && dis[v] == -1) dis[v] = dis[u] + 1, q.push(v);
    }
    return ans;
  };

  int i = -1, ans = bfs(i);
  while (i < q) {
    int j =
        find_fst(i, q - 1, [&](int mid) { return bfs(mid) <= (ans - 1) >> 1; });
    rep (j - i) cout << ans << " ";
    i = j, ans = bfs(i);
  }
  cout << "\n";
}