主页 讨论版 问题 名次 状态 统计
问题 J: 敬老师的旅行

问题 J: 敬老师的旅行

时间限制: 1 Sec  内存限制: 128 MB
提交: 80  解决: 22
[提交][状态][讨论版]

题目描述

自从时间来到了2018年,敬老师由于要找实习生活逐渐变得忙碌起来,在刷了一些leetcode之后他轻松get了某公司的offer。在实习前夕敬老师突然想出去旅行放松一下。他圈定了n个城市,想要设计一个旅行路线。非常神奇的是,这n个城市恰好由n-1条高铁线相连通,并且高铁的费用统一为1元(仅在相连的两城市之间),他想知道从某个城市pi出发携带ki元钱最多能前往多少个城市(起点城市也算,但不用花钱)。

输入

多组数据
第一行:数据组数T(1<=T<=25)
每组数据:
第一行:一个整数代表n个城市(1<=n<=1e5)
接下来的n-1行: 两个整数,代表在u,v之间有一条费用为1元的高铁。(1<=u,v<=n)
第n+1行:一个整数m(1<=m<=10)代表m个询问。
接下来的m行:pi(1<=pi<=n),ki(1<=ki<=1e6)分别代表每个询问的起始城市编号和携带的钱。

输出

对于每个询问输出一行,代表最多能前往的城市个数。

样例输入

1
6
1 2
1 3
2 4
2 5
3 6
2
2 2
2 4

样例输出

3
4

提示

[提交][状态][讨论版]