与区间动态查询第\(k\)小非常像，只是这里搬到了树上上面，仍然考虑类似做法
先考虑不带修的情况。假设我们现在在递归树的第一层，考虑如何统计答案。现在要将权值不超过\(mid\)的节点加入到树中，然后对于每一个询问，查询路径上有多少个加入了的点，从而将询问分成两组。问题是如何查询路径上有多少加入的点，利用LCA，不难想到设\(f[i]\)表示节点\(i\)到根的路径上有多少个被加入的点，则\(a,b\)路径上的被加入的点的个数就是\(f[a]+f[b]-f[lca]-f[lcafa]\)，其中\(lca\)为\(a,b\)的最近公共祖先，\(lcafa\)为\(lca\)的父亲。接下来的问题变成如何加入点。由以上分析，我们在加入一个点的时候，要将其子树的所有节点的计数都加一，于是可以想到利用DFS序，树上的单点增加变成了区间的区间修改，树上的单点查询变成了区间的单点查询，利用树状数组就好了
再考虑待修的情况，只需要像“动态排名”这道题目一样，将一个修改拆成两个修改就好了
然后就是认真读题吧，这道题目是查询第\(k\)大，不是第\(k\)小
标签：单点,网络管理,加入,路径,查询,CTSC2008,lca,节点 From： https://www.cnblogs.com/dingxingdi/p/18429742