可以发现，当 \(K = 0\) 时，答案为 \(2(n-1)\) ，而当在两端点连了一条边后，则操作方法为如果这条路径上的某条边被标记过，则取消这条边标记；否则把这条边标记为标记过，答案即为未被标记的边*2+标记过的边+连边的个数
当 \(K = 1\) 时：
答案显然为树的直径
当 \(K = 2\) 时：
我们还是考虑树的直径，然后把这条直径上的边都设为标记过，即把他们的边权设为 \(-1\) ，然后再跑直径
这里注意，两遍 \(dfs\) 的方法无法求有负边权的直径，原因是证明两边 \(dfs\) 正确时的贪心性质不再成立。因此，对于第二次求答案时可以使用树形 \(dp\) 的解法
最终复杂度 \(O(n)\)
标签：标记,APIO2010,dfs,P3629,答案,直径,巡逻 From： https://www.cnblogs.com/fox-konata/p/17728651.html