#P6626. [省选联考 2020 B 卷] 消息传递

[省选联考 2020 B 卷] 消息传递

题目描述

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

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

输入格式

本题包含多组测试数据。

第一行一个整数 TT,为测试数据组数。

对于每组测试数据:

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

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

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

输出格式

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

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

提示

样例解释

第一个询问,第一天新收到消息的人只有 22 号。 第二个询问,第一天新收到消息的人有 1133 号,第二天新收到消息的人有 44 号。

数据范围与约定

对于测试点 111n,m101\le n, m\le 10
对于测试点 221n,m1001\le n, m\le 100
对于测试点 331n,m10001\le n, m\le 1000
对于测试点 464\sim61n,m105,k201\le n, m\le 10^5, k\le 20
对于测试点 7107\sim101n,m1051\le n, m\le 10^5
对于所有测试点:1T5,1xn,0k<n1\le T\le 5, 1\le x\le n, 0\le k < n