夢に僕らで帆を張って
来るべき日のために夜を超え

标签 树的直径 下的文章

October 22, 2019

洛谷P4408/NOI2003 逃学的小孩

题意给出一颗树,求直径$+$任意点距直径两端点中距离最小的最大值数据范围:$3 \le N \le 200000$题解分析题意可以得出,对于确定的点$A,B,C$,必走的路径为$A \rightarrow B$,则最短的路径需要从$C \rightarrow A$与$C \rightarrow B$中选出一条最短的加上而对于可能的最大值,此时的$A \rightarrow B$一定为直径,$...
October 22, 2019

CF455C Civilization/洛谷P2195 HXY造公园

题意给出一个森林,$2$种操作求$u$所在的树的直径合并$u,v$所在的树并使直径最小数据范围:$1 \le m < n \le 3 \cdot 10^5$题解由合并操作想到并查集对于第一个操作,输出$u$所在的联通块(树)的直径对于第二个操作,合并后的直径最小为$u$所在树的直径$v$所在树的直径$u$所在树的半径$+v$所在树的半径$+1$取$\max$代码:#include<...