Given a tree with N nodes we are required to seperate a connected component with exactly k nodes. You are given queries specifying this k. We need to find the minimum edges to be removed for each query.
First line specifies N.
Next N-1 lines specify edges.
Next line shows Q(number of queries).
Subsequent Q lines contain k for each query.

Constraint:
N <= 3000
Q <= 3000
K <= N

Example:
Input:
5
1 2
1 3
1 4
1 5
3
1
2
4

Output:
1
3
1

There was this recent question-https://mirror.codeforces.com/contest/1097/problem/D It involved the intuition for multiplicative functions. How to determine the multiplicativity of the given function?

I found the following problem very interesting on a recent Hackerrank contest, I don't get the intuition for what the editorialist states.It would indeed be very helpful if someone helps me understand it.

Link to the problem

What I got is as follows:

(Note:dp[x...y] means dp[x] + dp[x+1] ... + dp[y])

for number of ways of reaching a solution from either string a or string b, the recurrence may go as follows

dp[i][j][k][0] = summation of dp[i-1][j-1][k][0...2];

dp[i][j][k][1] = (if a[i] equals c[k] then summation of dp[i-1][j][k-1][0...2] else 0) + dp[i-1][j][k][0...2];

dp[i][j][k][2] = (if b[j] equals c[k] then summation of dp[i][j-1][k-1][0...2] else 0) + dp[i][j-1][k][0...2];

Here, dp[i][j][k][x] means number of ways of forming c[0...k] from a[0...i] or from b[0...j] or both.

where x = 0 if we neglect last character of both a and b

x = 1 if we consider last character of a and not b

x = 2 if we consider last character of b and not a

Please correct me if I am wrong.Thanks in advance for the help.