[NFLS 1447/4] 镇长的步行计划 题解

大意

在树上新增 $k, k \le 2$ 条边, 新增的边能且只能经过 $1$ 次, 求遍历这棵树最小步数.

题解

k = 1

显然, 添加直径最优.

k = 2

所以, 先求一遍直径, 将直径上的边权设为 $-1$ , 再求一次直径, 即可.