7829 - 试题J:世界末日的时候,我会牵着你的手 25‘

通过次数

9

提交次数

74

时间限制 : 10 秒
内存限制 : 512 MB

wlxsq在去年种了一棵苹果树,现在这棵树长大了。

这颗树上有n个苹果,其中有n-1条树枝,每条树枝连接两个苹果。

现在wlxsq想要摘一段连续区间的苹果,他想知道想要最少选取几条树枝,使得树枝能将这些苹果全部连接起来?

简而言之,就是说寻找一个最小的连通块,这个连通块包括了这些苹果,求这个连通块中树枝的条数

因为此时正处苹果的丰收期,所以他每天都要摘苹果,因此有多组询问。

输入

第一行,输入nq,表示有n个苹果和q天。

接下来n-1行,每行输入uv,表示有一根树枝连接了这两个苹果。

接下来q行,每行读入lr,表示wlxsq想要摘第l,l+1,l+2\dots r个苹果。

输出

对于每一组询问,输出最少选取的树枝数。

样例

输入

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

输出

2
4
1

输入

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

输出

2
1
2
1
3

提示

样例解释

对于第一组询问,至少需要第1条和第2条树枝,这样两条边1-22-3能将13苹果连接起来。

对于第二组询问,这4条树枝都必须取,此时四条边能将15这5个苹果连接起来。

数据范围

subtask1(2\ pts): 1\le n\le 5, 1\le q\le 5

subtask2(3\ pts): 1\le n\le 10, 1\le q\le 50

subtask3(4\ pts): 1\le n\le 1000, 1\le q\le 1000

subtask4(5\ pts): 1\le n\le 10000, 1\le q\le 10000保证数据随机

subtask5(5\ pts): 1\le n\le 10000, 1\le q\le 10000不保证数据随机

subtask6(6\ pts): 1\le n\le 50000, 1\le q\le 50000

来源

竞码编程-蓝桥杯模拟赛3(大学生组&青少年组)