Дано дерево из $$$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 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
2 0
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
1 1
5 2 3 5 4 5 4 2 1 4 2 2 3 1 2 2 2 4 5 4
2 1
Рассмотрим первый пример.
В первом запросе нужно разделить три данные вершины ($$$7$$$, $$$4$$$ и $$$3$$$) на не более чем три группы, считая, что корнем дерева является вершина $$$2$$$. Когда дерево подвешено за вершину $$$2$$$, вершина $$$4$$$ является предком вершин $$$3$$$ и $$$7$$$. Поэтому нельзя все вершины отнести к одной группе. Есть только $$$1$$$ способ разделить эти вершины на две группы: $$$[4]$$$ и $$$[3, 7]$$$. Кроме того, есть один способ разделить данные вершины на три группы: $$$[7]$$$, $$$[4]$$$ и $$$[3]$$$. Таким образом, есть всего $$$2$$$ способа разбить данные вершины на не более чем три группы.
Во втором запросе дерево подвешено за вершину $$$4$$$, при этом $$$6$$$ является предком $$$2$$$, а $$$2$$$ является предком $$$1$$$. Поэтому нельзя все вершины отнести к одной группе.
Название |
---|