Number of connected subgraphs of size k in a tree

Revision en1, by Not-Afraid, 2020-09-24 06:44:24

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.

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)