Passable Paths (hard version) solution codeforces – Polycarp grew a tree from 𝑛n vertices. We remind you that a tree of 𝑛n vertices is an undirected connected graph of 𝑛n vertices and 𝑛−1n−1 edges that does not contain cycles.
He calls a set of vertices passable if there is such a path in the tree that passes through each vertex of this set without passing through any edge twice. The path can visit other vertices (not from this set).
In other words, a set of vertices is called passable if there is a simple path that passes through all the vertices of this set (and possibly some other).
For example, for a tree below sets {3,2,5}{3,2,5}, {1,5,4}{1,5,4}, {1,4}{1,4} are passable, and {1,3,5}{1,3,5}, {1,2,3,4,5}{1,2,3,4,5} are not.
Passable Paths (hard version) solution codeforces
Passable Paths (hard version) solution codeforces
The first line of input contains a single integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — number of vertices.
Following 𝑛−1n−1 lines a description of the tree..
Each line contains two integers 𝑢u and 𝑣v (1≤𝑢,𝑣≤𝑛1≤u,v≤n, 𝑢≠𝑣u≠v) — indices of vertices connected by an edge.
Following line contains single integer 𝑞q (1≤𝑞≤1051≤q≤105) — number of queries.
The following 2⋅𝑞2⋅q lines contain descriptions of sets.
The first line of the description contains an integer 𝑘k (1≤𝑘≤𝑛1≤k≤n) — the size of the set.
The second line of the description contains 𝑘k of distinct integers 𝑝1,𝑝2,…,𝑝𝑘p1,p2,…,pk (1≤𝑝𝑖≤𝑛1≤pi≤n) — indices of the vertices of the set.
It is guaranteed that the sum of 𝑘k values for all queries does not exceed 2⋅1052⋅105.
Output 𝑞q lines, each of which contains the answer to the corresponding query. As an answer, output “YES” if the set is passable, and “NO” otherwise.
You can output the answer in any case (for example, the strings “yEs“, “yes“, “Yes” and “YES” will be recognized as a positive answer).
Passable Paths (hard version) solution codeforces
5 1 2 2 3 2 4 4 5 5 3 3 2 5 5 1 2 3 4 5 2 1 4 3 1 3 5 3 1 5 4
YES NO YES NO YES
Passable Paths (hard version) solution codeforces
5 1 2 3 2 2 4 5 2 4 2 3 1 3 3 4 5 3 2 3 5 1 1
YES NO YES YES