Black Nodes in Subgraphs

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given a tree T with N nodes. The nodes are numbered from 1 to N, and each node is colored either white or black. You are given Q queries, where each query is of the form (s, b). You need to check if there is a connected subgraph of size exactly s, which contains exactly b black nodes.
A subgraph H, of a tree T, is a graph whose vertex set V_{H} is a subset of the nodes of the tree and the edges are exactly those edges of the tree whose both end points are in V_{H}. A subgraph H is a connected subgraph if H is connected.
Input
 The first line contains a single integer, T, which denotes the number of testcases. The descriptions of the testcases follow.
 The first line of each testcase contains two integers, N and Q, which denotes the number of nodes in the tree, and the number of queries, respectively.
 The ith of the next N  1 lines contains two integers: u_{i} and v_{i}. This denotes that there is an edge between nodes u_{i} and v_{i} in the tree.
 The next line contains N integers, c_{1}, c_{2}, .., c_{N}. c_{i} is 0 if node i is colored white, and it is 1 if it is colored black.
 The ith of the next Q lines contains two integers: s_{i} and b_{i}. This denotes a query of the form (s_{i}, b_{i}) as described above.
Output
 For each testcase, output a single line containing the string "Yes" (without quotes), if there is a connected subgraph as required by the query, or "No" (without quotes) otherwise.
Constraints
 1 ≤ T ≤ 5
 2 ≤ N ≤ 5000
 1 ≤ Q ≤ 10^{5}
 1 ≤ u_{i}, v_{i} ≤ N
 0 ≤ c_{i} ≤ 1
 0 ≤ b_{i} ≤ N
 1 ≤ s_{i} ≤ N
 b_{i} ≤ s_{i}
Example
Input: 1 9 4 4 1 1 5 1 2 3 2 3 6 6 7 6 8 9 6 0 1 0 1 0 0 1 0 1 3 2 7 3 4 0 9 5 Output: Yes Yes No No
Explanation
Query 1: The subgraph containing the nodes {6, 7, 9} is a connected subgraph because (6, 7) and (6, 9) are edges in the original tree. And it has exactly two black nodes (7 and 9). So, there is at least one connected subgraph of size exactly 3 which has exactly 2 black nodes. Hence the answer is "Yes".
Query 2: The subgraph containing the nodes {1, 2, 3, 4, 6, 7, 8} is a connected subgraph. And it has exactly three black nodes (2, 4 and 7). So, there is at least one connected subgraph of size exactly 7 which has exactly 3 black nodes. Hence the answer is "Yes".
Query 3: There is no connected subgraph of size exactly 4 with all white nodes. Hence the answer is "No".
Query 4: The only subgraph with 9 nodes is the entire tree itself. And it has 4 black nodes, and not 5. Hence the answer is "No".
Author:  admin3 
Tags  admin3 
Date Added:  2062017 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 