Not-Afraid's blog

By Not-Afraid, history, 4 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Isn’t that $$$\sum_u dp[u][k]$$$?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Seems like you are correct. I made a really silly mistake in this comment which made me think that i will overcount the answer.
    mistake from that comment:
    Let's say tree has just 2 nodes.
    and a single edge : 1 -> 2

    dp[1][1] = 1, dp[1][2] = 1;
    dp[2][1] = 1, dp[2][2] = 1;
    in the above example dp[2][2] should be 0 instead of 1 which made me think that i will overcount(facepalm).
    Thanks for answering :).