奇怪的树上背包，而且带了一些玄学。借这篇题解详细地总结一下树上背包的做法。
题面
给定一棵 \(n\) 个点的树，给定正整数 \(k\) , 在树上找出 \(k\) 个不同的点，设为\(A_1, A_2...A_k\)，使得 \(\sum_{i=2}^{k}{dis(A_i,A_{i-1})}\) 最小，输出这个最小值。其中 \(dis(x, y)\) 表示树上 x, y 之间最短路的长度。
\(1\le k\le n\le 3000\)。
解法
考虑答案肯定会包含很多个点，而这些个点里肯定只有唯一的一个深度最小的点（这不是废话吗），而这个点要么是这条路径的起点或者终点（起点还是终点效果一样），要么是路径上的一个点（也就是起点和终点都在子树内，且跨越了它的儿子们），于是可以考虑对于这两种情况进行讨论。