P2633 Count on a tree 主席树的树上差分
__ryp__
·
·
个人记录
题意很简单。
我们如果要查询的是子树上的第 k 小，那这就是很裸的 dfn 序套 DS 维护，DS 选主席树就很合适。
但是现在维护的是 u 到 v 路径上的，这段路径上的 dfn 序并不是连续的，并且第 k 小这种东西也是可加的，没法说分开求解。
那怎么办呢？我们想起了树上差分。
我们知道，u 到 v 路径上的信息，就是他们到 LCA 上路径信息的叠加。我们再考虑主席树，可以将 u，v，LCA 与 LCA 父节点做差分，那么得到的就是 u 到 v 路径上的信息。维护即可。
非常美丽的线段树差分！