自动搬运

查看原文

来自洛谷，原作者为

	Lgx_Q 变强不如变菜

搬运于2025-08-24 23:06:26，当前版本为作者最后更新于2024-11-22 09:08:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$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$ 的最优答案。考虑两种情况：

• $z$ 在 $y$ 子树内，此时可以直接树形 DP 求出。

• $z$ 在 $y$ 子树外，考虑 $z, y$ 两点的最近公共祖先 $c$，可以先让 $z$ 走到 $c$，再从 $c$ 走到 $y$。具体的，先进行一次树形 DP，再从上到下更新一遍（也可以理解为换根 DP）。

时间复杂度 $\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}$。