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 they all must be connected.
I came up with a solution which is like:
let's say 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$$$) then obviously answer will be overcounted.