线性数据结构 2：根路径度数

问题形式：给定一棵树， $q$ 次询问 $x,k$ 表示求 $x$ 到根路径上第 $k$ 小的度数，可离线。

弱化版：求 $k$ 这个度数的 $\rm rank$ ，即询问有多少个 $\le$ 它的。

度数的核心优势就是可遍历，但我们还不知道如何使用。

让我们先来解决弱化版，考虑直接 $\rm dfs$ ，维护祖先栈的信息，现在我们要支持加入一个度数，求度数前缀和。

度数是可遍历的！果断把前缀和改成后缀和，遍历更新，做完了。

那么问题来了，第 $k$ 小怎么求呢？

考虑直接维护答案数组，答案数组是一个分段函数，如果我们往其中扔了一个度数，造成的结果是某个位置往后集体平移。

这集我会，先把第 $k$ 小变成第 $k$ 大，然后需要平移的就只有 $\deg_x$ 段，而平移的代价是修改段端点，于是我们记录每个度数的端点即可简单修改，查询直接访问答案数组即可。