如果距离越长越优的题要考虑树的直径
我们发现这题对于一个\(k\)，我们对于每个点，让他从最远的点连过来得到的图的连通性等价于原图的连通性
而对于一个点最远的点就是他到直径两个端点的距离
因此我们求出树的直径，然后对于两个端点\(dfs\)，求出他们的深度，对于每个点，距离他们最远的距离就是到两个端点深度的最大值\(-1\)，把所有深度的个数放到桶里面，最后让答案累加即可
复杂度\(O(n)\)
CF1805D A Wide, Wide Graph
发布时间 2023-09-21 19:36:20作者: FOX_konata