算法
题意可以转化成
给定一个基环树森林, 求每颗基环树上的直径长度之和
找环
按照基环树的方法找即可
求直径
(i) 直径不经过环
对于以环上每一个点的子树, 记录直径即可
(ii) 直径经过环
断环为链, 考虑单调队列处理, 具体的
关于为什么需要断环为链:
方便快速处理环上两点间的距离, 显然不复制两份正确性会有问题
最后的答案即为 ( \(dis\) 为环上距离前缀和, \(D\) 为子树直径, \(Size\) 为环长)
\[\max{(dis_i - dis_j + D_i + D_j, i - j + 1 \leq Size)} \]代码
后补
总结
基环树板子 + 复杂的环上处理, 单调队列的应用
标签：IOI2008,断环为,环上,Island,基环树,直径,dis From： https://www.cnblogs.com/YzaCsp/p/18521141