Codeforces Round 629 (Div. 3) |
---|
Закончено |
Вам дано корневое дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Корень дерева находится в вершине с номером $$$1$$$.
Дерево — это связный неориентированный граф с $$$n-1$$$ ребром.
Вам заданы $$$m$$$ запросов. $$$i$$$-й запрос состоит из множества $$$k_i$$$ различных вершин $$$v_i[1], v_i[2], \dots, v_i[k_i]$$$. Ваша задача — определить, существует ли путь от корня до некоторой вершины $$$u$$$ такой, что каждая из заданных $$$k$$$ вершин или принадлежит этому пути, или расположена на расстоянии $$$1$$$ от некоторой вершины на этом пути.
Первая строка теста содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — количество вершин в дереве и количество запросов.
Каждая из следующих $$$n-1$$$ строк описывает ребро дерева. Ребро $$$i$$$ задается двумя целыми числами $$$u_i$$$ и $$$v_i$$$ — номерами вершин, которые это ребро соединяет $$$(1 \le u_i, v_i \le n, u_i \ne v_i$$$).
Гарантируется, что заданные ребра формируют дерево.
Следующие $$$m$$$ строк описывают запросы. $$$i$$$-я строка описывает $$$i$$$-й запрос и начинается с целого числа $$$k_i$$$ ($$$1 \le k_i \le n$$$) — количества вершин в текущем запросе. Затем следуют $$$k_i$$$ целых чисел: $$$v_i[1], v_i[2], \dots, v_i[k_i]$$$ ($$$1 \le v_i[j] \le n$$$), где $$$v_i[j]$$$ — это $$$j$$$-я вершина в $$$i$$$-м запросе.
Гарантируется, что все вершины в одном запросе различны.
Также гарантируется, что сумма всех $$$k_i$$$ не превосходит $$$2 \cdot 10^5$$$ ($$$\sum\limits_{i=1}^{m} k_i \le 2 \cdot 10^5$$$).
Для каждого запроса выведите ответ — «YES», если существует путь от корня до некоторой вершины $$$u$$$ такой, что каждая из $$$k$$$ заданных вершин или принадлежит этому пути, или расположена на расстоянии $$$1$$$ от какой-либо вершины на этом пути, и «NO» в противном случае.
10 6 1 2 1 3 1 4 2 5 2 6 3 7 7 8 7 9 9 10 4 3 8 9 10 3 2 4 6 3 2 1 5 3 4 8 2 2 6 10 3 5 4 7
YES YES YES YES NO NO
Изображение, относящееся к примеру:
Рассмотрим запросы.
Первый запрос — $$$[3, 8, 9, 10]$$$. Ответ — «YES», так как вы можете выбрать путь от корня $$$1$$$ до вершины $$$u=10$$$. Тогда вершины $$$[3, 9, 10]$$$ принадлежат пути от $$$1$$$ до $$$10$$$ и вершина $$$8$$$ расположена на расстоянии $$$1$$$ от вершины $$$7$$$, которая также принадлежит этому пути.
Второй запрос — $$$[2, 4, 6]$$$. Ответ — «YES», так как вы можете выбрать путь до вершины $$$u=2$$$. Тогда вершина $$$4$$$ находится на расстоянии $$$1$$$ от вершины $$$1$$$, которая принадлежит этому пути, а вершина $$$6$$$ находится на расстоянии $$$1$$$ от вершины $$$2$$$, которая принадлежит этому пути.
Третий запрос — $$$[2, 1, 5]$$$. Ответ — «YES», так как вы можете выбрать путь до вершины $$$u=5$$$ и все вершины из запроса будут принадлежать этому пути.
Четвертый запрос — $$$[4, 8, 2]$$$. Ответ — «YES», так как вы можете выбрать путь до вершины $$$u=9$$$, и вершины $$$2$$$ и $$$4$$$ расположены на расстоянии $$$1$$$ от вершины $$$1$$$, которая принадлежит этому пути, а вершина $$$8$$$ расположена на расстоянии $$$1$$$ от вершины $$$7$$$, которая принадлежит этому пути.
Ответ и на пятый, и на шестой запросы — «NO», потому что вы не можете выбрать подходящую вершину $$$u$$$.
Название |
---|