[湖南集训] 更为厉害

题目描述

设 $\text T$ 为一棵有根树,我们做如下的定义: - 设 $a$ 和 $b$ 为 $\text T$ 中的两个不同节点。如果 $a$ 是 $b$ 的祖先,那么称“$a$ 比 $b$ 更为厉害”。 - 设 $a$ 和 $b$ 为 $\text T$ 中的两个不同节点。如果 $a$ 与 $b$ 在树上的距离不超过某个给定常数 $x$,那么称“ $a$ 与 $b$ 彼此彼此”。 给定一棵 $n$ 个节点的有根树 $\text T$,节点的编号为 $1$ 到 $n$,根节点为 $1$ 号节点。 你需要回答 $q$ 个询问,询问给定两个整数 $p$ 和 $k$,问有多少个有序三元组 $(a,b,c)$ 满足: 1. $a,b,c$ 为 $\text T$ 中三个不同的点,且 $a$ 为 $p$ 号节点; 2. $a$ 和 $b$ 都比 $c$ 更为厉害; 3. $a$ 和 $b$ 彼此彼此。这里彼此彼此中的常数为给定的 $k$。

输入输出格式

输入格式


输入文件的第一行含有两个正整数 $n$ 和 $q$,分别代表有根树的点数与询问的个数。 接下来 $n - 1$ 行,每行描述一条树上的边。每行含有两个整数 $u$ 和 $v$,代表在节点 $u$ 和 $v$ 之间有一条边。 接下来 $q$ 行,每行描述一个操作。第 $i$ 行含有两个整数,分别表示第 $i$ 个询问的 $p$ 和 $k$。

输出格式


输出 $q$ 行,每行对应一个询问,代表询问的答案。

输入输出样例

输入样例 #1

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

输出样例 #1

3
1
3

说明

样例中的树如下图所示: ![](https://cdn.luogu.com.cn/upload/pic/6858.png) 对于第一个和第三个询问,合法的三元组有 $(2,1,4)$、 $(2,1,5)$ 和 $(2,4,5)$。 对于第二个询问,合法的三元组只有 $(4,2,5)$。 所有测试点的数据规模如下(注意,洛谷并不按照以下方式评测): ![](https://cdn.luogu.com.cn/upload/pic/6859.png) 对于全部测试数据的所有询问,$1\le p,k \le n$。 - 2023.9.15 添加一组 hack 数据。