网站首页
编程语言
数据库
系统相关
其他分享
编程问答
PARADOXXX
2024-09-09
PANDORA PARADOXXX
PANDORAPARADOXXX题意给出一棵树,每次操作删除树上的一条边,询问树上所有连通块中直径的最大值。思路倒序操作,删边变为连边。预处理出做完所有操作后的答案。使用并查集维护连通性,记录每个连通块内直径的端点。合并两个集合时,新的直径端点只可能是原来两个集合四个端点中的
2024-08-18
P10238 [yLCPC2024] F. PANDORA PARADOXXX
这里主要是了解一下套路,首先说一下树的直径的性质。1.任何一个点到它所在的联通块中距离最远的点一定是树的直径两点之一。2.两个连通块合并以后,新的树的直径一定为原先两个连通块中树的直径中的两个。了解完这个,我们来看这道题,根据树的直径的性质,我们可以来维护连通块,那一个