P16005 [ICPC 2020 NAC] Rooted Subtrees

一棵 **树** 是一个包含 $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$），表示当前询问的两个根节点。

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

**样例解释** 第一棵树的不同根化形式如下： :::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 完成