3062. rxms 喜欢玩耍

单点时限: 10.0 sec

内存限制: 256 MB

rxms 喜欢玩耍,她有一棵 $N$ 个节点的树,节点编号为 $1$ 到 $N$。她提出这样 $Q$ 次询问,每次给定一个区间 $[L, R]$,求编号在 $L$ 到 $R$ 之间的节点形成多少个连通块。

输入格式

第一行为测试数据组数 $T$。

对每一组数据,第一行为 $N,Q$ $(1 \leq N, Q \leq 10^5)$,$N$ 表示节点个数,$Q$ 表示询问次数。

接下来 $N-1$ 行每行有两个整数 $a, b$,表示 $a$ 跟 $b$ 间有一条边相连。

接下来 $Q$ 行每行有两个数 $L, R$ $(1 \leq L \leq R \leq N)$ 表示询问节点编号为区间 $[L, R]$ 的连通块个数。

输出格式

对于每组数据,先输出一行 Case #X:,其中 X 表示第几组数据,再输出 $Q$ 行,其中第 $i$ 行表示该组数据中的第 $i$ 次询问的连通块个数。

样例

Input
2
3 2
1 2
1 3
1 2
2 3
5 3
1 2
1 3
2 4
2 5
1 4
2 5
3 5
Output
Case #1:
1
2
Case #2:
1
2
3

2 人解决,2 人已尝试。

3 份提交通过,共有 5 份提交。

8.0 EMB 奖励。

创建: 5 年,4 月前.

修改: 3 年前.

最后提交: 3 年前.

来源: 第四届程序设计竞赛

题目标签