A5913. 「联合省选 2020 B」消息传递
编程题
省选/NOI-
知识点
题目描述
给定一个包含 $n$ 个人（从 $1$ 到 $n$ 编号）的树形社交网络。如果一个人在某天收到了一条消息，则下一天他会将消息传递给所有与他有直接社交关系的人。
现在有 $m$ 次询问，每次询问假定第 $0$ 天 $x$ 号人收到了一条消息，请你计算第 $k$ 天时新收到此条消息的人数（即第 $k$ 天前收到过此条消息的人不计入其中）。不同询问间互不影响。
现在有 $m$ 次询问，每次询问假定第 $0$ 天 $x$ 号人收到了一条消息，请你计算第 $k$ 天时新收到此条消息的人数（即第 $k$ 天前收到过此条消息的人不计入其中）。不同询问间互不影响。
输入格式
本题包含多组测试数据。第一行一个整数 $T$，为测试数据组数。
对于每组测试数据：
第一行两个数 $n,m$ 分别表示树形社交网络的人数和询问的数量。
接下来 $n - 1$ 行，每行两个数 $a, b$，表示 $a$ 号人和 $b$ 号人之间有直接社交关系。保证输入的是树形社交网络。
接下来 $m$ 行，每行两个数 $x, k$，意义见题目描述。
对于每组测试数据：
第一行两个数 $n,m$ 分别表示树形社交网络的人数和询问的数量。
接下来 $n - 1$ 行，每行两个数 $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$：$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$。
对于测试点 $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$。