P9600 [IOI 2023] 封锁时刻 题解

Description

P9600 [IOI 2023] 封锁时刻

匈牙利有 $N$ 个城市，编号依次为 $0$ 到 $N - 1$。

这些城市之间由 $N - 1$ 条双向道路连接，编号为 $0$ 至 $N - 2$。对每个 $j$（$0 \le j \le N - 2$），第 $j$ 条道路连接城市 $U[j]$ 和城市 $V[j]$，其长度为 $W[j]$，表示这两个城市之间的交通时间为 $W[j]$ 个时间单位。每条道路连接两个不同的城市，且每两个城市之间最多由一条道路连接。

两个不同城市 $a$ 和 $b$ 之间的一条路径是一个由不同城市组成的序列 $p_0, p_1, \ldots, p_t$，满足以下条件：

• $p_0 = a$，
• $p_t = b$，
• 对每个 $i$（$0 \le i \lt t$），存在一条道路连接 $p_i$ 和 $p_{i + 1}$。

利用这些道路从任意一个城市到任意一个其他的城市都是有可能的。换言之，任意两个不同城市之间都存在路径。
可以证明两个不同城市之间的路径是唯一的。

一条路径 $p_0, p_1, \ldots, p_t$ 的长度是这条路径上连接相邻城市的 $t$ 条道路的长度之和。

在匈牙利，很多人都会在建国日去参加在两个主要城市举行的庆祝活动。当庆祝活动结束时，他们会回家。政府为了防止人群干扰当地人，所以决定在特定时刻封锁城市。每个城市被政府分配一个非负的封锁时刻。政府决定所有城市的封锁时刻总和不得超过 $K$。具体来说，对每个 $i$（$0 \leq i \leq N - 1$），分配给城市 $i$ 的封锁时刻是一个非负整数 $c[i]$。所有 $c[i]$ 之和不超过 $K$。

考虑一个城市 $a$ 和某个封锁时刻的分配方案，我们说城市 $b$ 是从城市 $a$ 可达的当且仅当以下两种情况中的任意一种情况成立。

情况 1：$b = a$。

情况 2：这两个城市之间的路径 $p_0, \ldots, p_t$ （$p_0 = a$ 且 $p_t = b$）满足以下条件：

• 路径 $p_0, p_1$ 的长度最多为 $c[p_1]$，并且
• 路径 $p_0, p_1, p_2$ 的长度最多为 $c[p_2]$，并且
• $\ldots$
• 路径 $p_0, p_1, p_2, \ldots, p_t$ 的长度最长为 $c[p_t]$。

今年，两个主要的庆祝地点位于城市 $X$ 和 $Y$。
对于每一个封锁时刻的分配方案，可以定义一个便利分数，其定义为下面两个数字之和：

• 从城市 $X$ 可达的城市个数。
• 从城市 $Y$ 可达的城市个数。

注意如果一个城市既能从城市 $X$ 可达也能从城市 $Y$ 可达，那么它在计算便利分数时计算两次。

你的任务是计算能被某个封锁时刻分配方案实现的最大便利分数。

$2 \le N \le 200\,000$，$0 \le K \le 10^{18}$。

Solution

首先设 $f_i$ 表示 $i$ 到 $x$ 的距离，$g_i$ 表示 $i$ 到 $y$ 的距离。显然点 $i$ 的权值只可能为 $0/f_i/g_i$。

如果 $x=y$，是个经典的贪心：按照 $f_i$ 从小到大排序，选择最长的前缀和不超过 $k$ 的前缀填上权值即可，由于一个点的祖先的权值一定不超过这个点，所以这么做找到的一定是一个包含根的连通块。

当 $x\neq y$ 时上面的贪心就不对了。

先把 $x\to y$ 这条链上的点拿出来，显然这条链上最终能走到 $x$ 的是一段前缀，能走到 $y$ 的是一段后缀，如果前后缀不交，就说明 $x$ 能到的和 $y$ 能到的是独立的，所以上面那个做法就对了。这里先按照 $f$ 和 $g$ 的大小分别排序，相当于是找到满足 $pref_i+preg_j\leq k$ 时最大的 $i+j$，双指针即可。

如果前后缀有交，这说明 $x\to y$ 链上的所有点都要选权值，先把权值设为 $\min\{f_i,g_i\}$，并将 $k$ 减去已经预定的权值。对于不在链上的点，$a_i=\min\{f_i,g_i\},b_i=\max\{f_i,g_i\}$。对于链上的点，$a_i=\max\{f_i,g_i\}-\min\{f_i,g_i\},b_i=+\infty$。

现在转化为选择一些数选 $a_i$，选择另一些数选 $b_i$，剩下的选 $0$，要求总和不超过 $k$ 的情况下最大化选 $a_i$ 的个数+两倍选 $b_i$ 的个数。正确性就考虑所有不在链上的点，其父亲的两维均偏序它的两维，而链上的点的 $a_i$ 是个单谷的数，所以链上选两次的一定是一段区间。

求这个东西就考虑先按照 $b_i$ 排序，显然不会存在 $i$ 在 $j$ 之前，且 $i$ 选 $0$ 但 $j$ 选 $b_j$ 的情况，所以一定存在一个前缀，使得这个前缀都至少选一次，去掉这个前缀的后缀都至多选一次。

在动态开点线段树上二分即可。

时间复杂度：$O(n\log V)$。

Code

#include "closing.h"
#include <bits/stdc++.h>

#ifdef ORZXKR
#include "grader.cpp"
#endif

using i64 = int64_t;
using i128 = __int128_t;

const int kMaxN = 2e5 + 5;
const i64 kInf = 1e18;

int n, x, y;
int p[kMaxN];
i64 k, dis1[kMaxN], dis2[kMaxN];
std::vector<std::pair<int, int>> G[kMaxN];

struct SGT {
  static const int kMaxT = kMaxN * 60;
  int tot, rt, ls[kMaxT], rs[kMaxT], cnt[kMaxT];
  i128 sum[kMaxT];

  void clear() {
    for (int i = 1; i <= tot; ++i)
      ls[i] = rs[i] = sum[i] = cnt[i] = 0;
    tot = rt = 0;
  }
  void pushup(int x) {
    sum[x] = sum[ls[x]] + sum[rs[x]];
    cnt[x] = cnt[ls[x]] + cnt[rs[x]];
  }
  void update(int &x, i64 l, i64 r, i64 ql, int v) {
    if (!x) x = ++tot;
    if (l == r) {
      sum[x] += v * ql, cnt[x] += v;
      return;
    }
    i64 mid = (l + r) >> 1;
    if (ql <= mid) update(ls[x], l, mid, ql, v);
    else update(rs[x], mid + 1, r, ql, v);
    pushup(x);
  }
  int query(int x, i64 l, i64 r, i64 k) {
    if (!x) return 0;
    else if (l == r) return !l ? cnt[x] : std::min<int>(cnt[x], k / l);
    else if (k >= sum[x]) return cnt[x];
    i64 mid = (l + r) >> 1;
    if (k <= sum[ls[x]]) return query(ls[x], l, mid, k);
    else return cnt[ls[x]] + query(rs[x], mid + 1, r, k - sum[ls[x]]);
  }
} sgt;

void dfs(int u, int fa, i64 *dis) {
  p[u] = fa;
  for (auto [v, w] : G[u]) {
    if (v == fa) continue;
    dis[v] = dis[u] + w;
    dfs(v, u, dis);
  }
}

int solve1() {
  std::vector<i64> v1 = {0}, v2 = {0};
  for (int i = 1; i <= n; ++i)
    v1.emplace_back(dis1[i]), v2.emplace_back(dis2[i]);
  std::sort(v1.begin(), v1.end()), std::sort(v2.begin(), v2.end());
  for (int i = 1; i <= n; ++i)
    v1[i] += v1[i - 1], v2[i] += v2[i - 1];
  int ret = 0;
  for (int i = 0, j = n; i <= n; ++i) {
    for (; ~j && v1[i] + v2[j] > k; --j) {}
    if (j >= 0) ret = std::max(ret, i + j);
  }
  return ret;
}

int solve2() {
  static int id[kMaxN];
  static i64 a[kMaxN], b[kMaxN];
  int ret = 0, cnt = 0;
  i64 k = ::k;
  for (int i = 1; i <= n; ++i) {
    a[i] = std::min(dis1[i], dis2[i]);
    b[i] = std::max(dis1[i], dis2[i]);
    id[i] = i;
  }
  for (int i = x; i; i = p[i]) {
    ++cnt, k -= std::min(dis1[i], dis2[i]);
    a[i] = std::max(dis1[i], dis2[i]) - std::min(dis1[i], dis2[i]), b[i] = kInf;
  }
  if (k < 0) return 0;
  sgt.clear();
  std::sort(id + 1, id + 1 + n, [&] (int i, int j) { return b[i] < b[j]; });
  for (int i = 1; i <= n; ++i) sgt.update(sgt.rt, 0, kInf, a[id[i]], 1);
  ret = cnt + sgt.query(sgt.rt, 0, kInf, k);
  for (int i = 1; i <= n; ++i) {
    sgt.update(sgt.rt, 0, kInf, a[id[i]], -1);
    sgt.update(sgt.rt, 0, kInf, b[id[i]] - a[id[i]], 1);
    ++cnt, k -= a[id[i]];
    if (k >= 0) ret = std::max(ret, cnt + sgt.query(sgt.rt, 0, kInf, k));
    else break;
  }
  return ret;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N, x = X + 1, y = Y + 1, k = K;
  for (int i = 1; i <= n; ++i) G[i].clear();
  for (int i = 0; i < n - 1; ++i) {
    ++U[i], ++V[i];
    G[U[i]].emplace_back(V[i], W[i]);
    G[V[i]].emplace_back(U[i], W[i]);
  }
  dis1[x] = dis2[y] = 0;
  dfs(x, 0, dis1), dfs(y, 0, dis2);
  return std::max(solve1(), solve2());
}