P13644 K-LCA

成本越低，赚的越多！

T 国由 $n$ 座城市组成，首都在 $1$ 号城市，有 $(n-1)$ 条道路连接着这些城，且所有城市都可以通过这些道路到达首都。 有 $q$ 轮旅行活动，第 $i$ 次旅游会有一个参数 $(l_i,r_i)$，每次都有 $k$ 个人，他们每个人都会在编号在 $[l_i,r_i]$ 的城市中选择一个城市作为出发点。为了让每个人都有独处空间，任意两人不会选择同一个城市。 然后他们开始进行旅行。由于靠近首都的城市更高级，所以旅行者会向首都方向移动。 最终他们会在一个城市会聚，然后旅行结束。旅游公司没有足够经费让旅行者去更高级的城市，所以旅游公司会让他们会聚的城市离首都尽可能远。 现在旅游公司问你，他们会聚的地方，离首都距离最远是多少？两个城市之间的距离定义为最短路径上城市的个数（包括路径端点的两个城市）。

第一行三个数 $n,q,k$。 接下来 $(n-1)$ 行，每行两个正整数 $u,v$ 表示一条边。 接下来 $q$ 行，每行两个正整数 $l,r$ 表示一次询问。

共 $q$ 行，第 $i$ 行表示第 $i$ 次询问的答案。

**本题有捆绑测试**，每个子任务均为 $20$ 分。 | 子任务编号 | $n$ | $q$ | 特殊性质 | 时间限制 | 子任务依赖 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $0$ | $10^4$ | $10^4$ | 无 | 3s | 无 | | $1$ | $2\times10^4$ | $5\times10^4$ | 无 | 3s | $0$ | | $2$ | $5\times10^4$ | $5\times10^4$ | 无 | 5s | $1$ | | $3$ | $10^5$ | $10^5$ | **有** | 7s | 无 | | $4$ | $10^5$ | $10^5$ | 无 | 7s | $2,3$ | 特殊性质：树的形态是以 $1$ 结点为链顶的一条链 对于 $100\%$ 的数据，$n\le 10^5,q\le10^5,1< k\le n,r-l+1\ge k$。