本题直接暴力树形 dp 复杂度为 $O(nk)$，不知道为啥题解区有那么多“长链剖分优化 dp”但复杂度仍为 $O(nk)$ 的做法，建议撤下以免误人子弟。