网站首页
编程语言
数据库
系统相关
其他分享
编程问答
IOI2008
2024-11-01
[IOI2008] Island
算法题意可以转化成给定一个基环树森林,求每颗基环树上的直径长度之和找环按照基环树的方法找即可求直径(i)直径不经过环对于以环上每一个点的子树,记录直径即可(ii)直径经过环断环为链,考虑单调队列处理,具体的关于为什么需要断环为链:方便快速处理环上两点间
2024-06-02
[题解]P4381 [IOI2008] Island
P4381[IOI2008]Island题意:给定一个基环树森林,求每个基环树的直径之和。我们发现,一棵基环树的直径只有下面两种情况:环上的某一点作为根的子树的直径。环上有两点,每个点引出一条链,然后再将这两点相连。对于第一种情况,我们仅需用树形dp的方法求出每个子树的直径(见OIWiki-