Help me with this tree dp problem!!

Revision en5, by Misa-Misa, 2023-12-25 10:23:09

Given a tree with $$$N$$$ vertices, find the number of rooted trees (which consist of some edges present in the given tree) with $$$K$$$ vertices, including vertex 1. Constraints: $$$1 \leq K \leq N \leq 3000$$$.

Example :
Let $$$N$$$ = $$$5$$$ and the tree be this :

Then for K = 1, 2, 3, 4, 5 the solutions are :

This problem was taken from snuke 's blog

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Misa-Misa 2023-12-25 10:23:09 117
en4 English Misa-Misa 2023-12-25 09:02:30 56
en3 English Misa-Misa 2023-12-25 08:16:40 0 (published)
en2 English Misa-Misa 2023-12-25 08:16:14 243
en1 English Misa-Misa 2023-12-25 08:12:46 181 Initial revision (saved to drafts)