Блог пользователя Misa-Misa

Help me with this tree dp problem!!
Автор Misa-Misa, история, 6 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
6 месяцев назад, # |
← Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

This is probably a knapsack that runs in O(n^2) instead of the O(n^3) you expected. In case you want to overkill it use FFT.

→ Ответить