大家好，我是毒瘤，喜欢用玄学算法过题。

发现题解区没有这个做法，于是来发一篇。

思路

不难发现如果一个点对 \((u,v)\) 的距离为 \(d\)，那么在这棵树以 \(u\) 为根时，\(v\) 的深度为 \(d\)。于是考虑换根 DP。

首先思考如何计算答案。显然我们可以将查询离线下来，然后当换根到以 \(u\) 为根时，将有关 \(u\) 的所有查询全部解决即可。

其次，发现当一个 \(v\) 转化成根时，它会在其父节点 \(u\) 为根时的形态的基础上，所在 \(v\) 子树中的节点深度减 \(1\)，其余节点加 \(1\)。

然而，我们需要求的是深度为 \(d\) 的节点，于是单单想大多数的换根 DP 维护深度的极值是不行的，所以需要更新出所有的深度。

于是这个东西需要使用数据结构维护。明确这个数据结构所需的功能：

1. 区间加减。

2. 区间查询权值为 \(k\) 的编号。

Code