CF1111E Tree

给定一棵有 $n$ 个节点的树，以及 $q$ 个询问。 每个询问以三个整数 $k$、$m$ 和 $r$ 开头，接着是树上的 $k$ 个节点 $a_1, a_2, \ldots, a_k$。对于每个询问，假设树以 $r$ 为根。我们需要将给定的 $k$ 个节点分成最多 $m$ 个组，满足以下条件： - 每个节点恰好属于一个组，每个组至少有一个节点。 - 在任意一个组内，不能存在两个不同的节点，使得其中一个节点是另一个节点的祖先（无论是直接还是间接的祖先）。 你需要输出每个询问的方案数，对 $10^9+7$ 取模。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$），分别表示树的节点数和询问数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n, u \ne v$），表示树上的一条边，连接节点 $u$ 和节点 $v$。保证给定的图是一棵树。 接下来的 $q$ 行，每行以三个整数 $k$、$m$ 和 $r$ 开头（$1 \le k, r \le n$，$1 \le m \le \min(300, k)$），表示本次询问的节点数、最多分组数和树根节点。接下来是 $k$ 个互不相同的整数 $a_1, a_2, \ldots, a_k$（$1 \le a_i \le n$），表示本次询问涉及的节点。 保证所有询问中 $k$ 的总和不超过 $10^5$。

输出 $q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

考虑第一个样例。 在第一个询问中，需要将给定的三个节点（$7$、$4$ 和 $3$）分成最多三个组，假设树以 $2$ 为根。当树以 $2$ 为根时，$4$ 是 $3$ 和 $7$ 的祖先。因此不能将所有节点放在同一个组。只有 $1$ 种方式将节点分成两个组，即 $[4]$ 和 $[3, 7]$。也只有一种方式将节点分成三个组，即 $[7]$、$[4]$ 和 $[3]$。所以总共有 $2$ 种分组方式。 在第二个询问中，当树以 $4$ 为根时，$6$ 是 $2$ 的祖先，$2$ 又是 $1$ 的祖先。因此不能将所有给定节点放在同一个组。 由 ChatGPT 4.1 翻译