牛客 2B 树 (组合计数)

传送门

大意: 给定n节点树, 求划分为不超过$k$个连通块的方案数. n,k<=300.

 核心观察是每个连通块深度最低的点固定以后染色方案就固定了.

所以答案为$sumlimits_{i=1}^kinom{k}{i}i!inom{n-1}{i-1}$