本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-11 13:27:25

题意很简单。

我们如果要查询的是子树上的第 $k$ 小，那这就是很裸的 dfn 序套 DS 维护，DS 选主席树就很合适。

但是现在维护的是 $u$ 到 $v$ 路径上的，这段路径上的 dfn 序并不是连续的，并且第 $k$ 小这种东西也是可加的，没法说分开求解。

那怎么办呢？我们想起了树上差分。

我们知道，$u$ 到 $v$ 路径上的信息，就是他们到 LCA 上路径信息的叠加。我们再考虑主席树，可以将 $u$，$v$，LCA 与 LCA 父节点做差分，那么得到的就是 $u$ 到 $v$ 路径上的信息。维护即可。

非常美丽的线段树差分！