题目描述

一棵 树 是一个包含 $n$ 个节点和 $n-1$ 条边的连通无环无向图，任意两个节点之间有且仅有一条简单路径。一棵 有根树 是指选定一个特定节点作为根的树。

设 $T$ 是一棵树，$T_r$ 表示以节点 $r$ 为根的 $T$。在 $T_r$ 中，节点 $u$ 的 子树 是指所有满足“从根 $r$ 到 $v$ 的路径包含 $u$（包含 $u$ 本身）”的节点 $v$ 构成的集合。在本问题中，我们将以 $r$ 为根的树中，节点 $u$ 的子树节点集记作 $T_r(u)$。

你需要回答 $q$ 个询问。每个询问给出两个（可能相同）节点 $r$ 和 $p$。一个集合 $S$ 被称为 可获得的，当且仅当它可以表示为以 $r$ 为根的树中的某个子树与以 $p$ 为根的树中的某个子树的交集。形式化地说，集合 $S$ 是可获得的，当且仅当存在节点 $u$ 和 $v$，使得 $S = T_r(u) \cap T_p(v)$。

对于给定的两个根，请统计不同的非空可获得集合的数量。两个集合被认为是不同的，当且仅当存在至少一个元素属于其中一个而不属于另一个。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$），分别表示树中节点的数量以及需要回答的询问个数。节点编号从 $1$ 到 $n$。

接下来的 $n-1$ 行，每行包含两个空格分隔的整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示节点 $u$ 和 $v$ 之间有一条无向边。保证这些边构成一棵合法的树。

接下来的 $q$ 行，每行包含两个空格分隔的整数 $r$ 和 $p$（$1 \le r, p \le n$），表示当前询问的两个根节点。

输出格式

对于每个询问，输出一行一个整数，表示通过上述过程可以生成的不同可获得集合的数量。

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

8
6

提示

样例解释

第一棵树的不同根化形式如下：

:::align{center} :::

考虑以 $1$ 和 $3$ 为根的情况，可获得的 8 个集合为：

1. $\{1\}$，取 $u = 1, v = 1$；
2. $\{1, 2, 4, 5\}$，取 $u = 1, v = 2$；
3. $\{1, 2, 3, 4, 5\}$，取 $u = 1, v = 3$；
4. $\{2, 3, 4, 5\}$，取 $u = 2, v = 3$；
5. $\{2, 4, 5\}$，取 $u = 2, v = 2$；
6. $\{3\}$，取 $u = 3, v = 3$；
7. $\{4, 5\}$，取 $u = 2, v = 4$；
8. $\{5\}$，取 $u = 5, v = 5$。

若以 $4$ 和 $5$ 为根，则只有 6 个可获得集合：

1. $\{1\}$，取 $u = 1, v = 1$；
2. $\{1, 2, 3\}$，取 $u = 2, v = 4$；
3. $\{1, 2, 3, 4\}$，取 $u = 4, v = 4$；
4. $\{1, 2, 3, 4, 5\}$，取 $u = 4, v = 5$；
5. $\{3\}$，取 $u = 3, v = 2$；
6. $\{5\}$，取 $u = 5, v = 5$。

对于其中某些集合，可能存在多种不同的 $(u, v)$ 选择方式得到相同的集合。

翻译由 DeepSeek V3.2 完成