题解：P17138 [KOI 2026 #1] 步道

· · 题解

给定一棵顶点和边均带有正权值的树，需要最大化连接两个不同顶点的路径权值。其中，路径 P 的权值 w(P) 定义为“路径中所有边的权值之和 s(P)”减去“路径中所有顶点的权值最大值 m(P)”，即 w(P)=s(P)-m(P)。

子任务 1

一共有 \dfrac{N(N-1)}{2} 条可能的路径。对于其中的每条路径，都可以在线性时间内计算其权值。

因此，总时间复杂度为 O(N^3)。

子任务 2

将路径的一个端点固定为树根。通过一次 DFS，可以对每个顶点同时计算出连接树根与该顶点的路径中“边权值之和”与“顶点权值最大值”。也就是说，当路径的一个端点固定时，可以在线性时间内求出所有 N-1 条可能路径的权值。

对每个顶点分别重复上述过程，即可在总时间复杂度 O(N^2) 内求出答案。

子任务 3

树的直径一定是答案。可以在线性时间内求出树的直径。

子任务 4

给定的树是一条链。

不失一般性，可以假设所有顶点权值 A_i 互不相同。为此，可以取一个足够小的正实数 \varepsilon，并认为每个 A_i 都增加了 i\varepsilon。

固定顶点 v。为了在所有满足 m(P)=A_v 的路径

P=\langle s_v\to s_v+1\to\cdots\to v\to v+1\to\cdots\to e_v\rangle

中最大化路径权值，应当按照如下方式确定两个端点：

使用栈从左到右扫描数组 A，即可在线性时间内求出每个 v 所对应的 s_v。对于 e_v，可以采用对称的方法计算。

这样，可以得到 N 条可能成为最优路径的候选路径

每条路径的 $s(P_v^*)$ 都可以利用边权数组 $L$ 的前缀和，在常数时间内计算。 因此，总时间复杂度为 $O(N)$。 ### 子任务 5 给定的树是一棵以顶点 $N$ 为中心的星形树。因此，一条路径最多包含两条边。 对于仅由一条边构成的路径，可以直接处理。 不失一般性，可以假设 $A_1<A_2<\cdots<A_{N-1}$。这可以通过按照 $A_i$ 的大小对除顶点 $N$ 之外的其余 $N-1$ 个顶点重新编号来实现。 由两条边构成的路径一定具有如下形式： $$P:=\langle x\to N\to v\rangle\quad(x<v<N)$$ 固定 $v$ 后，有 $$w(P)=L_x+L_v-\max\{A_v,A_N\}$$ 因此，选择满足 $x<v$ 且 $L_x$ 最大的顶点 $x$ 即为最优选择。 总时间复杂度为 $O(N\log N)$。 ## 子任务 6 需要使用如下关键观察。 固定常数 $X$，并删除所有满足 $A_v>X$ 的顶点。在剩余的每棵连通分量树中分别求出直径，并将所有这些直径中长度最大的路径记为 $P_X$。如果使 $s(P_X)-X$ 最大的 $X$ 为 $X_{\mathrm{opt}}$，那么 $P_{X_{\mathrm{opt}}}$ 就是本题的答案。 由于 $m(P_X)\le X$，对于本题的一条最优路径 $P_{\mathrm{opt}}$，当取 $X=m(P_{\mathrm{opt}})$ 时，$s(P_X)-X$ 也会达到最大值。 此外，只需要考虑 $X\in\{A_1,A_2,\ldots,A_N\}$ 即可。 在本子任务中，需要考虑的不同 $X$ 值至多有 $20$ 个。因此，对于每个 $X$，直接构造对应的森林并计算其中各棵树的直径即可。 总时间复杂度为 $O(20N)$。 ## 子任务 7 应用子任务 6 中的关键观察。 随着 $X$ 逐渐增大，森林中会不断加入新的顶点和边。在此过程中，两棵树会反复通过一条边合并为一棵连通树。 设两棵树 $T_1$、$T_2$ 通过边 $e$ 合并为一棵树 $T:=T_1\cup\{e\}\cup T_2$。 设 $T_1$ 和 $T_2$ 的直径分别为 $P_1:=\langle s_1\to\cdots\to e_1\rangle$ 和 $P_2:=\langle s_2\to\cdots\to e_2\rangle$。 根据树的直径的性质，树 $T$ 的直径一定是以下 $6$ 条路径之一： - 路径 $P_1$； - 路径 $P_2$； - 一端为 $s_1$ 或 $e_1$，另一端为 $s_2$ 或 $e_2$ 的 $4$ 条路径。 因此，如果能够高效计算树中任意两个顶点之间的距离，就可以在两棵树通过一条边合并后，高效求出新树的直径。顶点之间的距离可以使用最近公共祖先算法计算。 也就是说，按照顶点权值 $A_v$ 从小到大的顺序依次加入顶点，并维护每棵连通分量树的直径信息，就可以对所有 $X\in\{A_1,A_2,\ldots,A_N\}$ 高效计算 $s(P_X)$。 总时间复杂度为 $O(N\log N)$。 翻译由 ChatGPT-5.6 完成