Hi everyone.
The title itself has the problem description, but let me describe it once more below.
We are given a tree with $$$N$$$ nodes. 1 <= $$$N$$$ <= 100. We need to find the number of connected subgraphs which has exactly $$$k$$$ nodes and all these $$$k$$$ nodes must be connected.

I came up with a solution which is like:
let's root the tree at node $$$1$$$:
$$$dp[i][j]$$$ = number of ways to choose a subgraph of size $$$j$$$ in the subtree of $$$i$$$ (including node $$$i$$$). Now this is a knapsack-like dp.
but the problem here i am facing is that $$$dp[1][k]$$$ will be number of ways to choose a subgraph of size $$$k$$$ rooted at node $$$1$$$. I am unable to figure out a way to calculate this answer for whole tree. If i root every $$$x$$$ (1 <= $$$x$$$ <= $$$N$$$) and then add the answer for every $$$x$$$ then obviously answer will be overcounted.

Can anyone suggest what wrong with my approach or how can it be corrected or any other solution or any relevant link except the one's i mentioned below?

P.S. — I tried asking this in this blog but got no response.