更为厉害

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一棵以结点 $1$ 为根、含 $n$ 个结点的树。

对于树上两个不同的结点 $a,b$：

• 若 $a$ 是 $b$ 的祖先，则称“$a$ 比 $b$ 更为厉害”；
• 若 $a,b$ 的树上距离不超过给定常数 $x$，则称“$a$ 与 $b$ 彼此彼此”。

你需要回答 $q$ 个询问。每个询问给定 $p,k$，求有多少个有序三元组 $(a,b,c)$ 同时满足：

1. $a,b,c$ 是三个互不相同的结点，且 $a=p$；
2. $a$ 和 $b$ 都是 $c$ 的祖先；
3. $a$ 与 $b$ 的距离不超过 $k$。

输入格式

第一行输入两个正整数 $n,q$，分别表示结点数和询问数。

接下来 $n-1$ 行，每行输入两个整数 $u,v$，表示树上的一条无向边。

接下来 $q$ 行，每行输入两个整数 $p,k$，表示一次询问。

输出格式

对于每个询问输出一行一个非负整数，表示合法有序三元组的数量。

样例输入 1

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

样例输出 1

3
1
3

样例解释

样例中的树如下：

对于第一个和第三个询问，合法三元组为 $(2,1,4)$、$(2,1,5)$、$(2,4,5)$。对于第二个询问，唯一的合法三元组为 $(4,2,5)$。

数据范围

对于所有数据，保证 $1\le n,q\le 3\times 10^5$，$1\le p,k\le n$，输入的边构成一棵树。