← 返回题目列表

Codeforces · 1111/E

E. 树

中文机器翻译题面 查看原题

给您一棵包含 $$$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$$$ 查询的答案。

示例

输入 #1

7 2
5 4
2 6
5 3
1 2
7 5
4 6
3 3 2 7 4 3
3 1 4 6 2 1

输出 #1

2
0

输入 #2

7 2
4 7
2 5
4 1
5 1
5 6
4 3
3 3 2 7 1 4
2 1 6 3 2

输出 #2

1
1

输入 #3

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

输出 #3

2
1

注意

考虑第一个例子。

在第一个查询中,我们必须将三个给定节点($$$7$$$、$$$4$$$ 和 $$$3$$$)划分为最多三组,假设树的根位于 $$$2$$$。当树的根位于 $$$2$$$ 时,$$$4$$$ 是 $$$3$$$ 和 $$$7$$$ 的祖先。所以我们不能将所有节点归为一组。只有 $$$1$$$ 方法可以将给定节点分为两组,即 $$$[4]$$$ 和 $$$[3, 7]$$$。此外,只有一种方法可以将给定节点分为三组,即 $$$[7]$$$、$$$[4]$$$ 和 $$$[3]$$$。因此,总共有 $$$2$$$ 方法将给定节点分为最多三组。

在第二个查询中,当树的根位于 $$$4$$$ 时,$$$6$$$ 是 $$$2$$$ 的祖先,$$$2$$$ 是 $$$1$$$ 的祖先。因此,我们不能将所有给定的节点放入一组。