QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[0]

# 6163. 消息传递

Statistics

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

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

输入格式

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

对于每组测试数据:

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

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

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

输出格式

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

样例数据

样例 1 输入

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

样例 1 输出

1
1

样例 1 解释

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

第二个询问,第一天新收到消息的人有 13 号,第二天新收到消息的人有 4 号。

子任务

对于测试点 11n,m10

对于测试点 21n,m100

对于测试点 31n,m1000

对于测试点 461n,m105,k20

对于测试点 7101n,m105

对于所有测试点:1T5,1xn,0k<n