P9531 [JOISC 2022] 复兴计划 题解

Description

给定一个 $n$ 个点 $m$ 条边的连通图，带边权。

有 $q$ 次询问，每次给定一个 $x$，并将所有边的边权 $w$ 变为 $|w-x|$，问新图的最小生成树大小。

询问之间独立。

$n\leq 500,m\leq 10^5,q\leq 10^6$。

Solution

首先对于一条边 $(u,v,w)$，如果存在一个 $x$ 使得其在最小生成树里，那么这条边的出现时刻一定是一段区间。

则是因为当 $x=w$ 时这条边的竞争力最强，当 $x$ 在 $w$ 基础上变大或者变小时，$|x-w|$ 和其它边的差一定不会变小，所以一定存在左右端点 $l,r$ 满足 $x$ 在 $[l,r]$ 内即代表这条边在最小生成树里。

考虑找到每条边的出现区间。

从大到小加边，用类似 LCT 维护生成树的方式，如果不连通就直接加，否则每次找到 $u,v$ 树上路径的最大值 $w'$ 进行替换，容易发现当 $x\leq\frac{w+w'}{2}$ 时 $(u,v,w)$ 才能替换，所以将 $w$ 的右端点设为 $\frac{w+w'}{2}$，$w'$ 的左端点设为 $\frac{w+w'}{2}+1$ 即可。

这个做法的正确性是显然的，因为是从大到小加边，所以这么得到的左端点一定小于等于右端点。而如果 $w'$ 现在不替换，那么当 $w$ 更小，替换的时刻还会更小，此时一定能用第一次找到的 $w$ 替换。

找到区间后维护一个一次函数即可。

时间复杂度：$O(nm+q)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

using i64 = int64_t;

const int kMaxN = 505, kMaxM = 1e5 + 5;

int n, m, q;
int l[kMaxM], r[kMaxM];
std::tuple<int, int, int> e[kMaxM];
std::vector<std::pair<int, int>> G[kMaxN];
std::map<std::tuple<int, int, int>, int> mp;

void add(int u, int v, int w) {
  G[u].emplace_back(v, w), G[v].emplace_back(u, w);
}
void del(int u, int v, int w) {
  G[u].erase(std::find(G[u].begin(), G[u].end(), std::pair<int, int>{v, w}));
  G[v].erase(std::find(G[v].begin(), G[v].end(), std::pair<int, int>{u, w}));
}

bool dfs(int u, int fa, int to, std::vector<std::tuple<int, int, int>> &vec) {
  if (u == to) return 1;
  for (auto [v, w] : G[u]) {
    if (v == fa) continue;
    vec.emplace_back(u, v, w);
    if (dfs(v, u, to, vec)) return 1;
    vec.pop_back();
  }
  return 0;
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    e[i] = {w, u, v};
  }
  std::sort(e + 1, e + 1 + m, std::greater<>());
  for (int i = 1; i <= m; ++i) {
    auto [w, u, v] = e[i];
    mp[{u, v, w}] = mp[{v, u, w}] = i;
    r[i] = 1e9;
    std::vector<std::tuple<int, int, int>> vec;
    if (dfs(u, 0, v, vec)) {
      int uu = 0, vv = 0, ww = 0;
      for (auto [u, v, w] : vec) {
        if (w > ww) {
          uu = u, vv = v, ww = w;
        }
      }
      del(uu, vv, ww);
      int j = mp[{uu, vv, ww}];
      r[i] = (w + ww) / 2, l[j] = (w + ww) / 2 + 1;
    }
    add(u, v, w);
  }
  std::vector<std::tuple<int, int, int>> vec;
  for (int i = 1; i <= m; ++i) {
    if (l[i] <= r[i]) {
      int w = std::get<0>(e[i]);
      vec.emplace_back(l[i], -1, w);
      if (w <= r[i]) {
        vec.emplace_back(w, 2, -2 * w);
        vec.emplace_back(r[i] + 1, -1, w);
      } else {
        vec.emplace_back(r[i] + 1, 1, -w);
      }
    }
  }
  std::sort(vec.begin(), vec.end());
  std::cin >> q;
  i64 k = 0, b = 0;
  for (int i = 1, j = 0; i <= q; ++i) {
    int x;
    std::cin >> x;
    for (; j < vec.size() && std::get<0>(vec[j]) <= x; ++j) {
      k += std::get<1>(vec[j]);
      b += std::get<2>(vec[j]);
    }
    // i64 ans = 0;
    // for (int j = 1; j <= m; ++j)
    //   if (l[j] <= x && x <= r[j])
    //     ans += abs(x - std::get<0>(e[j]));
    // std::cout << ans << '\n';
    std::cout << k * x + b << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}