题解：P9704 「TFOI R1」Tree Home - Block

WARNING

本文会带你保姆级推公式，应该是题解中推公式最详细的一篇~~才不是因为我数学和 OI 都太菜了~~，因而用到了大量数学公式，可能会加载较慢，请耐心等待。

挺逆天的一道数学题。

这个 $f$ 函数有 $3$ 个参数明显不好处理，那我们拿出做初一化简求值题的感觉直接化简：

\begin{align*} & f(a, b, c) = [a - b](a^2 + b^2 + ab + 3ac + 3bc + 3c^2) \\ & = a(a^2 + b^2 + ab + 3ac + 3bc + 3c^2) - b(a^2 + b^2 + ab + 3ac + 3bc + 3c^2) \\ & = (a^3 + ab^2 + a^2b + 3a^2c + 3abc + 3ac^2) - (a^2b + b^3 + ab^2 + 3abc + 3b^2c + 3bc^2)\\ & = a^3 + ab^2 + a^2b + 3a^2c + 3abc + 3ac^2 - a^2b - b^3 - ab^2 - 3abc - 3b^2c - 3bc^2 \\ & = a^3 + 3a^2c + 3ac^2 - b^3 - 3b^2c - 3bc^2 \end{align*}

这个部分很简单，乘法分配律然后去括号抵消一些项就好了。

接着把 $a = d_p - d_r, b = d_q - d_r, c = d_r$ 代入：

\begin{align*} & a^3 + 3a^2c + 3ac^2 - b^3 - 3b^2c - 3bc^2\\ & = (d_p - d_r) ^ 3 + 3(d_p - d_r)^2d_r + 3(d_p - d_r)d_r^2 - (d_q - d_r)^3 - 3(d_q - d_r)^2d_r - 3(d_q - d_r)d_r^2\\ & = (d_p^3 - 3d_p^2d_r + 3d_pd_r^2 - d_r^3) + 3d_r(d_p^2 + d_r^2 - 2d_pd_r) + 3d_r^2d_p - 3d_r^3 - (d_q^3 - 3d_q^2d_r + 3d_qd_r^2 - d_r^3) - 3d_r(d_q^2 + d_r^2 - 2d_qd_r) - 3d_r^2d_q + 3d_r^3\\ & = d_p^3 - 3d_p^2d_r + 3d_pd_r^2 - d_r^3 + 3d_rd_p^2 + 3d_rd_r^2 - 6d_pd_r^2 + 3d_r^2d_p - 3d_r^3 - d_q^3 + 3d_q^2d_r - 3d_qd_r^2 + d_r^3 - 3d_rd_q^2 - 3d_r^3 + 6d_qd_r^2 - 3d_r^2d_q + 3d_r^3\\ & = (d_p^3 - d_q^3) + (3d_pd_r^2 - 6d_pd_r^2 + 3d_r^2d_p) + (d_r^3 - d_r^3) + (3d_rd_p^2 - 3d_p^2d_r) + (3d_r^3 - 3d_r^3) + (3d_q^2d_r - 3d_rd_q^2) - (3d_qd_r^2 - 6d_qd_r^2 + 3d_r^2d_q) + (3d_r^3 - 3d_r^3)\\ & = d_p^3 - d_q^3 \end{align*}

式子很长，但思路很简单，就是先用完全平方公式（ $(a - b)^2 = a^2 + b^2 - 2ab$ ）和完全立方公式（ $(a - b)^3 = a^3 - 3a^2b + 3ab^2 - b^3$ ）以及乘法分配律代入替换拆括号（第一、二步）然后疯狂合并同类项发现基本都抵消了（第三步），然后就剩下了这么个~~可可爱爱~~简单的式子（暴力出奇迹.jpg）。

ps：有没有大佬有简单的方法化简呢？手敲 KaTeX 化简了十几分钟 Qwq。

说句闲话：原式中出现了大量的 $d_r$ ，化简完竟然和它无关……化简这个式子估计占了题目难度的一半。

于是题目要求的式子就是 $|d_p^3 - d_q^3| + |v_p - v_q|$ 。然后鉴于有绝对值，继续利用初一知识分类讨论，有以下四种情况：

原式（用 $S$ 表示）

S=\max \begin{cases} d_p^3 - d_q^3 + v_p - v_q = (d_p^3 + v_p) - (d_q^3 + v_q) & (d_p > d_q \And v_p > v_q) \\ d_q^3 - d_p^3 + v_p - v_q = (d_q^3 - v_q) - (d_p^3 - v_p) & (d_p < d_q \And v_p > v_q) \\ d_p^3 - d_q^3 + v_q - v_p = (d_p^3 - v_p) - (d_q^3 - v_q) & (d_p > d_q \And v_p < v_q) \\ d_q^3 - d_p^3 + v_q - v_p = (d_q^3 + v_q) - (d_p^3 + v_p) & (d_p < d_q \And v_p < v_q) \end{cases}

然后我们发现每个式子都有两个项下标一样，可以一起处理。于是我们令 $A_i = d_i^3 + v_i, B_i = d_i^3 - v_i$ ，然后把上面四个式子整理一下，分别是：

\begin{align*} A_p - A_q\\ B_q - B_p\\ B_p - B_q\\ A_q - A_p\\ \end{align*}

如果需要最大化原式那么我们需要让被减数尽量大，减数尽量小。由于区间被指定了所以这说到底是个 RMQ，而由于没有修改因此可以通过 $4$ 个 ST 表维护。

终于我们有了最终思路：

预处理出 $d$ 数组
利用 ST 表查询
比较得出结果

时间复杂度分为两部分，预处理 $d$ 数组可以用一个 dfs，时间复杂度 $O(n + m)$ ，由于是一棵树所以 $m = n - 1$ ，最终忽略常数复杂度就是 $O(n)$ 。ST 表预处理为 $O(n \log n)$ ，查询为 $O(1)$ ，可以通过。

ACCode（带注释）：

1
/*Code by Block_Fish*/
2
#include <bits/stdc++.h>
3

4
#define INF 0x3f3f3f3f
5
#define EPS 1e-8
6
#define FOR(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
7
#define log printf
8
#define IOS                      \
9
  ios::sync_with_stdio(false); \
10
  cin.tie(nullptr);            \
11
  cout.tie(nullptr);
12

13
using namespace std;
14

15
typedef __int128 i128;
16
typedef long long ll;
17
typedef pair<ll, ll> PII;
18

19
const ll N = 2e5 + 10;
20
ll n, t, u, v, w, a[N], l1, l2, r1, r2, lg2[N], dis[N], st1[30][N], st2[30][N], st3[30][N], st4[30][N];
21
vector<PII> g[N];
22

23
template <typename T>
24

25
inline T read() {
26
  T sum = 0, fl = 1;
27
  char ch = getchar();
28
  for (; !isdigit(ch); ch = getchar())
29
    if (ch == '-') fl = -1;
30
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
31
  return sum * fl;
32
}
33

34
template <typename T>
35

36
inline void write(T x) {
37
  if (x < 0) {
38
    putchar('-'), write<T>(-x);
39
    return;
40
  }
41
  static T sta[35];
42
  ll top = 0;
43
  do { sta[top++] = x % 10, x /= 10; } while (x);
44
  while (top) putchar(sta[--top] + 48);
45
}
46

47
// 4 个 ST 表，很长但是基本复制粘贴
48
void init() {
49
  lg2[2] = 1;
50
  FOR(i, 1, n) {
51
    st1[0][i] = st2[0][i] = dis[i] * dis[i] * dis[i] + a[i];
52
    st3[0][i] = st4[0][i] = dis[i] * dis[i] * dis[i] - a[i];
53
  }
54
  FOR(i, 3, n) lg2[i] = lg2[i >> 1] + 1;
55
  FOR(i, 1, lg2[n]) {
56
    ll len = 1 << i;
57
    FOR(j, 1, n - len + 1) {
58
      st1[i][j] = max(st1[i - 1][j], st1[i - 1][j + (len >> 1)]);
59
      st2[i][j] = min(st2[i - 1][j], st2[i - 1][j + (len >> 1)]);
60
      st3[i][j] = max(st3[i - 1][j], st3[i - 1][j + (len >> 1)]);
61
      st4[i][j] = min(st4[i - 1][j], st4[i - 1][j + (len >> 1)]);
62
    }
63
  }
64
}
65

66
// 好的函数命名可以方便写代码和调试
67
ll queryMax1(ll l, ll r) {
68
  ll k = lg2[r - l + 1], len = 1 << k;
69
  return max(st1[k][l], st1[k][r - len + 1]);
70
}
71

72
ll queryMin1(ll l, ll r) {
73
  ll k = lg2[r - l + 1], len = 1 << k;
74
  return min(st2[k][l], st2[k][r - len + 1]);
75
}
76

77
ll queryMax2(ll l, ll r) {
78
  ll k = lg2[r - l + 1], len = 1 << k;
79
  return max(st3[k][l], st3[k][r - len + 1]);
80
}
81

82
ll queryMin2(ll l, ll r) {
83
  ll k = lg2[r - l + 1], len = 1 << k;
84
  return min(st4[k][l], st4[k][r - len + 1]);
85
}
86

87
// 要先预处理出 d 数组
88
void dfs(ll now, ll fa) {
89
  for (auto v : g[now]) {
90
    if (v.first == fa) continue;
91
    dis[v.first] = dis[now] + v.second;   // 要继承父亲的 d 然后加上自己的
92
    dfs(v.first, now);
93
  }
94
}
95

96
int main() {
97
  n = read<ll>(), t = read<ll>();
98
  FOR(i, 1, n) a[i] = read<ll>();
99
  FOR(i, 2, n) {
100
    u = read<ll>(), v = read<ll>(), w = read<ll>();
101
    g[u].push_back({v, w}), g[v].push_back({u, w});
102
  }
103
  dfs(1, -1);
104
  init();   // ST 表和线段树都要初始化！
105
  while (t--) {
106
    l1 = read<ll>(), r1 = read<ll>(), l2 = read<ll>(), r2 = read<ll>();
107
    write<ll>(max({queryMax1(l1, r1) - queryMin1(l2, r2), queryMax1(l2, r2) - queryMin1(l1, r1), queryMax2(l1, r1) - queryMin2(l2, r2), queryMax2(l2, r2) - queryMin2(l1, r1)})), putchar('\n');  // 输出的 4 种情况取 max
108
  }
109
  return 0;
110
}

AC 记录~

代码很长，但是非常模块化，写起来不是很慢。

理解万岁！

音乐

音乐

支持与分享

评论区