更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19354572

给定一棵有 $n$ 个节点的树，巡警车从 $1$ 号节点出发遍历所有边后返回，每条边需经过两次，总距离为 $2*(n-1)$。现可新建 $K$ 条边$(k = \{ 1, 2\})$，要求新建的每条边必须恰好经过一次，求规划新建边的方案，使得巡警车的总巡逻距离最小，并输出该最小值。

我们可以发现，对于 $k = 1$ 的情况，显然你求出一条直径，再把直径的两个端点连上，这样是最优的。

但是当 $k = 2$ 的时候，我们需要再连一次，但是这样的话，我们最好选比较长的，最初的想法是选次长的直径，但是我们想想，如果你选的这条新的直径，和原来的直径，有很多重合的点，那么就不是很优，我们为了处理这个重复的玩意，其实可以把原直径的所有边赋为 $-1$，这样的话，我们再找最长的直径，就不会出问题了。

但是这样需要知道一个问题， dfs 求直径是无法解决边权为负的情况，于是我们考虑树形 dp 的方式，直接再记一次直径的长度即可。

设两次的直径长度为 $L_1, L_2$，则最终答案为：

$k = 1$ 时：$2 * (n - 1) - L_1 + 1$

$k = 2$ 时：$2 * (n - 1) - (L_1 - 1) - (L_2 - 1)$