一般有意思的树上背包。
题意：给定 \(n\) 个点的树，选 \(k\) 个点 \(a_1, a_2, \cdots, a_k\)，使得 \(\sum dis(a_i, a_{i + 1})\) 最小。\(n \le 3000\)。
首先选的肯定是一个树上的连通块，然后起点终点肯定是直径两个端点。于是直接 \(f_{u, i, 0/1/2}\) 表示 \(u\) 子树内选了 \(i\) 个点，起点终点一共选了 \(0/1/2\) 个。转移就是树上背包，时间复杂度 \(\mathcal{O}(n^2)\)。
代码没有，因为随机看的。