CF983E NN country 题解

link T3 desu

落月城有 $n$ 个地铁站，用一棵无根树表示，边连接站点。

有 $m$ 条地铁线路，第 $i$ 条线路覆盖树上 $x_i$ 到 $y_i$ 的简单路径上所有站点，线路双向。

$q$ 次询问，每次给出 $a_i, b_i$，求从 $a_i$ 到 $b_i$ 最少乘坐地铁次数（一次乘坐可在同一条线路上任意两站直达）。若无法到达输出 $-1$。

---

场了这题。之前在nflsoj上做过。

（话说我两次做这题都会做感觉这题用倍增不值*2800啊括号）

令 $c=\text{lca}(a,b)$，显然从 $a$ 坐到 $b$ 只需要经过 $c$ 即可。

那么我们考虑先从 $a$ 和 $b$ 以最快的方式往 $c$ 的方向赶。

显然的，我们可以发现，在乘坐的过程中，深度小的点一定最优。即：如果一味的选择深度最小的点，然后换乘下一条线路到达下一个深度最小的点，一直这样下去是最优的方案。不存在一个 为了下一步更优的结果而不选择深度最小的点 的情况。

为什么？

令当前线路深度最小的点为 $x$。

你选择一个深度次小的点 $p$。如果它能换乘下一条线路越过 $x$，那么你可以在最后的 $x$ 换乘。

如果它不能越过 $x$，那么最优的点就是 $x$。

因此任何情况下选深度最小的点就是最优的。

那么我们就可以开始倍增：

考虑维护三个东西：

1. up[i]，表示从 $i$ 出发向上的地铁最浅能到达哪里

2. up2[i] ，表示从 $i$ 出发乘坐一条地铁最浅能到达哪里

3. jumptrans[i][j]，表示从 $i$ 出发乘坐 $2^j$ 条地铁最浅能到达哪里

第一个东西很显然，把一条地铁按 $\text{lca}$ 拆成两条就好。

第二个东西，实际上是维护出发点在 $i$ 的子树内的所有 $up_i$ 的深度最小值。可以一边 dfs 计算出来。

第三个东西，由于我们知道直接贪心选择深度最小的最优，

那么初始值即为 jumptrans[i][j]=up2[i]，转移方程即为 jumptrans[i][j]=jumptrans[jumptrans[i][j-1]][j-1] 。

那么只需要把 $a$ 和 $b$ 都跳到 $c$ 即可。

交一发，发现是不对的。原因在于，$a$ 和 $b$ 到达 $c$ 的最后一步可能可以使用同一条地铁线（即横穿 $c$ 的地铁线）。

记录 $a,b$ 往上跳，到达 $c$ 的最后一个换乘站的位置为 $d,e$。（最后一步先不跳）

令地铁线的两端为 $x,y$，那么这条地铁线能被 $a,b$ 同时使用的条件是 $x$ 在 $d$ 的子树内 且 $y$ 在 $e$ 的子树内。（反过来也一样）

考虑记录每个点的 dfs 序，那么这就变成了一个二维数点问题。只需要范围内合法的点的个数不为 $0$ 即可使用。

统计答案是容易的。

代码