All submissions for this problem are available.###Read problems statements in [Hindi](http://www.codechef.com/download/translated/S19ELTST/hindi/ADJLEAF2.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/S19ELTST/mandarin/ADJLEAF2.pdf), [Russian](http://www.codechef.com/download/translated/S19ELTST/russian/ADJLEAF2.pdf), [Vietnamese](http://www.codechef.com/download/translated/S19ELTST/vietnamese/ADJLEAF2...) and [Bengali](http://www.codechef.com/download/translated/S19ELTST/bengali/ADJLEAF2.pdf) as well. Consider a rooted tree. A leaf in this tree is a vertex that does not have any children. Suppose that we perform a depth-first search from the root and write down the numbers of all leaves in the order in which they are visited. Since the order of visiting the sons of any vertex during the search is not fixed, many different sequences of leaves may be created. We call a subset of all leaves *good* if it is non-empty and there is at least one sequence of leaves such that the leaves from this subset (in some order) form its contiguous subsequence. You are given a tree with $N$ vertices numbered $1$ through $N$. You should answer $Q$ queries. In each query, you are given a vertex $R$ and a set of leaves $S$; you should find out whether $S$ is a good set when the tree is rooted at $R$. ### Input - The first line of the input contains two space-separated integers $N$ and $Q$. - Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ describing an edge in the tree. - The next $Q$ lines describe queries. Each of these lines contains two space-separated integers $R$ and $K$, followed by a space and $K$ space-separated integers $s_1, s_2, \dots, s_K$ denoting the leaves in $S$. ### Output For each query, print a single line containing the string `"YES"` if the given set is good or `"NO"` otherwise. ### Constraints - $3 \le N \le 5 \cdot 10^5$ - $1 \le Q \le 5 \cdot 10^5$ - $1 \le R \le N$ - $1 \le K \le N$ - $1 \le s_i \le N$ for each valid $i$ - all elements of $S$ are distinct leaves - vertex $R$ has at least two adjacent vertices - the sum of $K$ over all queries does not exceed $5 \cdot 10^5$ ### Example Input ``` 10 2 1 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 1 2 9 10 1 3 5 7 9 ``` ### Example Output ``` YES NO ```
|Tags||auxiliary-tree, dynamic-programming, kingofnumbers, snckel19, taran_1407|
|Time Limit:||2.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.