题解:
这题是lct并不难想
关键在于如何建图
如果把每个大象连向第一个不能处理的大象
那么cut操作要删除的就是一个点而不是边
所以可以采用先离散化,
之后对于存在的大象,用边连向第一个不能处理的大象(不论存不存在)
对于不存在的大象,用边连向下一个大象
令不存在的大象权值为0,存在的为1
那么答案就是路径的权值和了 (大体思路与弹飞绵羊挺像的)
题解:
这题是lct并不难想
关键在于如何建图
如果把每个大象连向第一个不能处理的大象
那么cut操作要删除的就是一个点而不是边
所以可以采用先离散化,
之后对于存在的大象,用边连向第一个不能处理的大象(不论存不存在)
对于不存在的大象,用边连向下一个大象
令不存在的大象权值为0,存在的为1
那么答案就是路径的权值和了 (大体思路与弹飞绵羊挺像的)