#3306. 「联合省选 2020 B」消息传递

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

给定一个包含 n 个人(从 1 n 编号)的树形社交网络。如果一个人在某天收到了一条消息,则下一天他会将消息传递给所有与他有直接社交关系的人。

现在有 m 次询问,每次询问假定第 0 x 号人收到了一条消息,请你计算第 k 天时新收到此条消息的人数(即第 k 天前收到过此条消息的人不计入其中)。不同询问间互不影响。

输入格式

本题包含多组测试数据。第一行一个整数 T ,为测试数据组数。

对于每组测试数据:

第一行两个数 n,m 分别表示树形社交网络的人数和询问的数量。

接下来 n - 1 行,每行两个数 a, b ,表示 a 号人和 b 号人之间有直接社交关系。保证输入的是树形社交网络。

接下来 m 行,每行两个数 x, k ,意义见题目描述。

输出格式

对于每组测试数据:输出 m 行,每行一个数表示询问的答案。

样例

样例输入

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

样例输出

1
1

样例解释

第一个询问,第一天新收到消息的人只有 2 号。 第二个询问,第一天新收到消息的人有 1 3 号,第二天新收到消息的人有 4 号。

数据范围与提示

对于测试点 1 1\le n, m\le 10

对于测试点 2 1\le n, m\le 100

对于测试点 3 1\le n, m\le 1000

对于测试点 4\sim6 1\le n, m\le 10^5, k\le 20

对于测试点 7\sim10 1\le n, m\le 10^5

对于所有测试点: 1\le T\le 5, 1\le x\le n, 0\le k < n