我在想什么？？？

题目要求强制在线，但我根本就没想过要离线。
第一眼看到数据范围 $10^5$，马上就觉得是主席树之类的东西维护第 $k$ 大。
显然可以二分第 $k$ 大，然后树链剖分，用主席树维护这条路径上有多少 $\leq mid$ 的点权。
这样看上去是对的，但是复杂度是高贵的三个 $\log$，令人不寒而栗。

实际上这题很简单，就是主席树板子。
考虑去做一个类似于树上前缀和的东西，直接在主席树树上二分即可，那不就做完了吗，只有一个 $\log$。

记得离散化，另外不要把树剖写错。