MX-S7-T2 Speaker 题解

· · 题解

n, q\le 400

考虑对于每一天，枚举 z_i 表示选择的城市，然后 \mathcal O(n) 在树上求出 x_i \to z_i 和 z_i \to y_i 两条路径的长度，时间复杂度 \mathcal O(n^2 q)，期望得分 \mathtt {16pts}。

n, q\le 2000

预处理，枚举城市 p，在树上 DFS 一遍求出所有路径 p \to q 的长度，即可做到 \mathcal O(n ^ 2 + nq)，期望得分 \mathtt {32pts}。

n\le 2\times 10^5，q\le 3

考虑使用树上倍增求出路径长度，时间复杂度 \mathcal O(nq\log n)，期望得分 \mathtt {40pts}。

n\le 2000，q\le 2\times 10^5

此时要求我们不能直接枚举 z_i，考虑直接求出所有可能的 (x, y) 的答案。枚举 x 为根，DFS 一遍树，设 f_y 表示 x\to y 路径上选择一个 z 的最优答案。考虑两种情况：

时间复杂度 \mathcal O(n^2 + q)，小常数 \mathcal O(nq) 做法可能也可以过这一档分。期望得分 \mathtt {52pts}。

特殊性质 C

以 1 为根，进行换根 DP 即可。

时间复杂度 \mathcal O(n + q)，加上之前的做法，期望得分 \mathtt {76pts}。

n,q\le 2\times 10^5

考虑对于每个点求出 d_u = \max\limits_{v = 1} ^ n \{c_v - 2\cdot\text{dist} (u, v)\}，其中 \text{dist} (u, v) 表示 u, v 两点在树上的距离。可以类似特殊性质 C 的做法，换根求出。

考虑路径 x_i \to y_i 以及 z_i 的关系，找到 z_i 走到路径 x_i \to y_i 时的第一个点 u，那么 d_u 即计算到了 z_i 的答案。

所以，总答案应为 c_{x_i} + c_{y_i} + \max\limits_{u \in \{x_i \to y_i\}} d_u，可以树上倍增求出一段路径的 d_u 的最大值，时间复杂度 \mathcal O((n + q)\log n)，期望得分 \mathtt{100pts}。