PROBLEM
You are given a given a tree of N nodes, each of which nodes is colored either black or white. Given Q queries, each of pair (s, b), you need to tell whether there exists a subgraph of size s consisting of b black nodes.
SOLUTION
Claim: For a subgraph of size s, find the min and the max number of black vertices it can have. Then, answer for all b's from the min to max will be yes, and no otherwise.
Proof: Let minB[s], maxB[s] denote the minimum and the maximum number of black nodes in a subgraph of size s. The important observation is that you can transition from any s sized subgraph to another s sized subgraph by adding a vertex and deleting a vertex, and it will change the number of black nodes by at most 1. So, the set of valid b’s for a fix s will be containing consecutive elements in the range minB[s] to maxB[s].
Finding minB[s] and maxB[s] can be done using tree dp in time complexity \mathcal{O}(n^2).
Let dpMin[u][s] denote the minimum number of black nodes in a subgraph of size s in the subtree of u (the vertex u is assumed to be included in that sugraph).
Similarly, we define the dpMax[u][s].
minB[s] can be computed by as minimum of dpMin[u][s] for each u from 1 to N. Similarly, maxB[s] can be computed.
Pseudo Code
dfs(u):
T[u] = 1
for v in child(u):
if v != parent[u]
dfs(v)
T[v] += T[u]
// Fill dpMin[u][li] with infinity.
[/li] // Fill dpMax[u][li] with zero.
[/li] S = 1 // Number of overall nodes process till.
dpMin[u][1] = 1 if color of u is black, else 0.
dpMax[u][1] = 1 if color of u is black, else 0.
for v in child(u):
if v == parent[u]:
continue
for s = S to 0:
// Iterate over all possible sizes in the subtree of v.
for c = 0 to T[v]:
dpMin[u][s + c] = min(dpMin[u][s + c], dpMin[u][s] + dpMin[v][c])
dpMax[u][s + c] = max(dpMax[u][s + c], dpMax[u][s] + dpMax[v][c])
S += T[v]
It might look like the above algorithm is \mathcal{O}(n^3), but with careful observations, you can prove that it is indeed \mathcal{O}(n^2).