@[xiaoweiws](/space/show?uid=134819) 求直径是O(N) 枚举C点最多N方，但是直径不够多跑不慢
by 枫初音斗颂皮 @ 2019-07-15 23:23:40
g11抱走
by Liu_zj @ 2019-07-16 08:00:07
~~过气烧钱还有人玩~~
by xiaoweiws @ 2019-07-16 13:59:17
@[枫初音斗颂皮](/space/show?uid=107880)
直径不够多是什么意思？
那本题只是最坏情况O(n^2)，平均O（nlogn)吗？
by xiaoweiws @ 2019-07-16 14:01:36
@[xiaoweiws](/space/show?uid=134819) emm..鉴于我也不会树的直径，我也不是很清楚这个算法的流程。具体地说，如果是任意一条直径都可以，那就是O(N)；但如果并不是任意一条直径的话，就要遍历所有直径，可能被菊花图卡掉。
by 枫初音斗颂皮 @ 2019-07-16 16:30:01
@[枫初音斗颂皮](/space/show?uid=107880)
树的直径就是两次DFS
第一次找到最远点第二次再找最远点
而且树的直径是唯一的（至少长度是吧）
我觉得可能tle的最坏情况就是$2*10^5$个点在一条直线上（比起菊花图还有mle的可能），这样的话搜两次还要枚举一次我觉得要爆
$O(n^2+n)$
~~也有可能是我想多了~~
by xiaoweiws @ 2019-07-16 19:24:57