1.基环树

定义：有\(n\)个点和\(n\)条边的图，就是给树连了一条边，此时图中恰好只有一个环

解决这类问题时，通常断环，变成普通的树的问题，然后再特殊处理环

P2607 [ZJOI2008] 骑士

click

断环成树后就跟没上司一样是个树形dp，注意森林，long long就行了，具体细节见这里

P5022 [NOIP2018 提高组] 旅行

click

• \(m = n - 1\)

就是树

肯定以\(1\)为起点，每次向下搜之前对能到的城市排个序，挑小的走

期望\(60pts\)，实测\(60pts\)

这里面排序那个for上限应该是n写错了所以56

• \(m = n\)

基环树，没森林

考虑枚举删掉的边，每删一条，就跑一遍情况1，是\(O(nm)\)的

谷上可过，gxyz过不了，T了3个，这是谷子结果，应该是更答案慢了些

可以剪枝优化，就是每走一步就看优不优，不优就不走了

like this

P4381 [IOI2008] Island

click

题目要求的是基环树森林中每个单元的直径之和

我们考虑一下基环树内的直径类型：过环的和不过环的

(ps:不过环的放这图是我一开始没想到)

对于不过环的，可以预处理，接下来考虑带环的

如果\(i,j\)是直径出入环的两点，那么该直径可以分解为环上一部分和以\(i,j\)为端点的两根链

暴力就是枚举\(i,j\)，将对应部分求得并加在一起，从中取最大与第一种情况比最大就行

可以混\(50\)