P9755 [CSP-S 2023] 种树 题解

Description

你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。

森林的地图有 $n$ 片地块，其中 $1$ 号地块连接森林的入口。共有 $n-1$ 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。

你的目标是：在每片地块上均种植一棵树木，并使得 $i$ 号地块上的树的高度生长到不低于 $a_i$ 米。

你每天可以选择一个未种树且与某个已种树的地块直接邻接（即通过单条道路相连）的地块，种一棵高度为 $0$ 米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第 $1$ 天你只能在 $1$ 号空地种树。

对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第 $x$ 天，$i$ 号地块上的树会长高 $\max(b_i + x \times c_i, 1)$ 米。注意这里的 $x$ 是从整个任务的第一天，而非种下这棵树的第一天开始计算。

你想知道：最少需要多少天能够完成你的任务？

$1\leq n \leq 10^5，1 \leq a_i \leq 10^{18}, 1 \leq b_i \leq 10^9，0 \leq |c_i| \leq 10^9, 1 \leq u_i, v_i \leq n$。保证存在方案能在 $10^9$ 天内完成任务。

Solution

考虑二分答案。

容易发现那个相邻块的限制就是每个点选的时间不早于它的所有祖先。

设 $t_i$ 表示第 $i$ 个人需要完成任务的最晚开始时间，这个同样可以二分求得。

然后思考怎样 check。

有一个想法是把 $t$ 从小到大排序，然后判断如果所有 $t_i$ 都有 $i\leq t_i$ 则合法，否则不合法。

但是这样做不能保证子孙在祖先之后。

---

容易发现 $t_i\leq \min_{j\in son(i)}\{t_j-1\}$，于是用一遍 dfs 把这个限制加上就会发现所有原始的 $t_i$ 都满足祖先 $<$ 子孙。

这样再 sort 一遍就一定会满足原题相邻块的限制条件了。

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

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e5 + 5;

int n;
int a[kMaxN], b[kMaxN], c[kMaxN], t[kMaxN], buc[kMaxN];
std::vector<int> G[kMaxN];

__int128 getval(int t, int b, int c) {
  int lim;
  if (c >= 0) lim = t;
  else lim = std::min(t, (b - 1) / (-c));
  return b * lim + (__int128)lim * (lim + 1) / 2 * c + t - lim;
}

bool chk(int l, int r, int a, int b, int c) {
  return getval(r, b, c) - getval(l - 1, b, c) >= a;
}

void dfs(int u, int fa) {
  for (auto v : G[u]) {
    if (v == fa) continue;
    dfs(v, u);
    t[u] = std::min(t[u], t[v] - 1);
  }
}

bool check(int x) {
  static int tt[kMaxN];
  for (int i = 1; i <= n; ++i) {
    int L = 0, R = x + 1, res = -1e9;
    if (!chk(1, x, a[i], b[i], c[i])) return 0;
    __int128 tot = getval(x, b[i], c[i]);
    while (L + 1 < R) {
      int mid = (L + R) >> 1;
      if (tot - getval(mid - 1, b[i], c[i]) >= a[i]) L = res = mid;
      else R = mid;
    }
    t[i] = res;
  }
  dfs(1, 0);
  int m1 = 0, m2 = n;
  for (int i = 1; i <= n; ++i) {
    if (t[i] <= 0) {
      return 0;
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (t[i] > n) tt[m2--] = t[i];
    else ++buc[t[i]];
  }
  for (int i = 1; i <= n; ++i)
    for (; buc[i]; --buc[i])
      tt[++m1] = i;
  for (int i = 1; i <= n; ++i)
    t[i] = tt[i];
  // std::sort(t + 1, t + 1 + n);
  for (int i = 1; i <= n; ++i)
    if (t[i] < i)
      return 0;
  return 1;
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i)
    std::cin >> a[i] >> b[i] >> c[i];
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  int L = 0, R = 1e9 + 1, res = 1e9;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (check(mid)) R = res = mid;
    else L = mid;
  }
  std::cout << res << '\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;
}