4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс, Актобе

Задача C. Маглы наступают

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Интернет в мире представляется в виде $n$ вершин и $n - 1$ ребер, каждое ребро соединяет две вершины, и возможно добраться из каждой вершину в каждую, передвигаясь по ребрам. В каждой вершине живет Волшебник. Волшебники — очень дружелюбные существа, но они могут существовать только парами. 2 Волшебника являются парой, если они находятся в соседних вершинах и решили быть парой. У Волшебника не может быть большой одной пары. Маглы решили заблокировать некоторые вершины дерева, а заодно и забрать Волшебников, живущих в них. Каждая блокировка представляет собой $k$ вершин дерева, которые будут заблокированы. Из каждой заблокированной вершины Маглы забирают Волшебника. После блокировки наступает паника и Волшебники ищут себе пару. Если хотя бы один Волшебник (среди тех, кого не забрали) не найдет себе пару, наступает Хаос. Обратите внимание, Волшебники разбиваются на пары так, чтобы образовать как можно количество пар. У Волшебников есть $q$ предположений того — какие вершины будут блокировать. И на каждый из этих предположений, Волшебникам интересно, будет ли Хаос если случится такая блокировка.

Формат входного файла

В первой строке входных данных дается два числа $n$, $q$ ($1 <= n, q <= 5*10^5$) — количество вершин и количество предположений блокировок соответственно. В следующих $n-1$ строках даются два числа $u$, $v$ ($1 <= u, v <= n$) — вершины, между которыми есть ребро. В следующих $q$ строках подаются описания блокировок в следующем виде: $k, a_1, a_2, \dots, a_k$ $(0 <= k <= n, 1 <= a_i <= n)$ — количество и номера заблокированных вершин.

Формат выходного файла

Выведите $q$ чисел, разделенных пробелами. Для каждой блокировки в порядке входных данных выведите $1$, если все Волшебники смогут разбиться на пары (Хаос не наступит), и $0$, если нет (Хаос наступит).

Система оценки

Определим $sum(k)$ как суммарное количество вершин во всех блокировках. 1. $1 <= n, q, sum(k) <= 3000$, в дереве нет вершин, у которых больше 2 соседей. Оценивается в $13$ баллов. 2. $1 <= n, q, sum(k) <= 3000$. Оценивается в $17$ баллов. 3. $1 <= n, q, sum(k) <= 100000$. Оценивается в $22$ баллов. 4. $1 <= n, q, sum(k) <= 100000$. $k_i <= 1$. Оценивается в $19$ баллов. 5. $1 <= n, q, sum(k) <= 500000$. Оценивается в $29$ баллов.

Пример:

Вход

3 3
1 2
2 3
1 1
1 2
1 3

Ответ

1 0 1

Замечание

После блокировки первой вершины или третьей вершины, остаются лишь 2 вершины, которые связаны ребром и поэтому могут образовать пару, что и делают. В случае удаления 2ой вершины, даже если Волшебники хотят образовать пару, они не могут, так как не связаны прямым ребром. ( Aidos Nurmash )