题解：P16445 [XJTUPC 2026] The Whole Rest

szh_AK_all · 2026-05-10 18:52:51 · 题解

假设我们选择的路径起点为 s，终点为 t，那么显然有如下结论：

• 在我们选择的路径中走了奇数次的边为 s 到 t 最简路径上的边。

• 该路径的代价即为 s 到 t 最简路径上的边的边权异或和。

  令 dis_i 表示节点 i 到根的路径上的边的边权异或和，则 s 到 t 的代价为 dis_s \oplus dis_t。

因为 s,t 可以相同，所以最小代价为 0，也就是说我们需要满足 dis_s=dis_t。

分析起点为 s，终点为 t 且经过了所有点的路径的边数最小是多少。对于 s 到 t 最简路径上的边，我们只需经过一次，而对于其他边，类似于 dfs，我们需要向下探一边还需要回溯一边，所以需要经过两次。综合起来边数即为 2(n-1)-dist(s,t)，其中 dist(s,t) 为 s 到 t 最简路径边数。

由于需要边数最小，所以我们要 dist(s,t) 最大，每次取 dis 相同的一类点然后求直径即可。

求出来 s,t 后，同样类似于 dfs 求出路径。