Number of connected subgraphs of size k in a tree

Revision en3, by Not-Afraid, 2020-09-24 06:51:42

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 can be solved with subset-sum kind of 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Not-Afraid 2020-09-24 06:52:11 0 (published)
en3 English Not-Afraid 2020-09-24 06:51:42 55
en2 English Not-Afraid 2020-09-24 06:49:11 349
en1 English Not-Afraid 2020-09-24 06:44:24 848 Initial revision (saved to drafts)