Path containing K Nodes
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
You are given a tree.
You have to execute numerous queries on this tree. In a query, you will be given K nodes and you need to find if there is a path in the tree which contains all these K nodes.
If there is a path containing these K nodes, then output Yes. Otherwise, output No.
First line contains T, number of test cases to follow.
First line of each test case contains an integer N which represents the number of nodes in the tree.
Next N-1 lines contain the description of the tree. Each line contains 2 space separated integers implying that there is an edge between these two nodes.
Next line contains Q, number of path queries to follow.
First line of each query contains an integer K.
Second line contains K space separated nodes.
For each query, output Yes if there is a path containing the K query nodes. Otherwise, output No.
- 1 ≤ N ≤ 105
- 1 ≤ Sum of N over all test cases ≤ 105
- 1 ≤ T ≤ 500
- 3 ≤ K ≤ N
- 1 ≤ Sum of K over all test cases and queries ≤ 106
- Nodes are numbered from 1
Input: 1 10 3 1 5 7 4 6 10 4 8 9 2 1 3 4 8 5 5 3 4 3 8 10 3 4 8 7 9 6 3 2 1 6 3 6 2 5 Output: Yes No Yes No
Query 1: The path corresponding to it is 8->5->3->4->10.
Query 2: There does not exists any path joining all 4.
|Tags||bfs, cook60, devuy11, medium|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.