求一种随机生成树算法
  • 板块学术版
  • 楼主zhangzhihao2卷王
  • 当前回复13
  • 已保存回复13
  • 发布时间2023/8/6 20:12
  • 上次更新2023/11/3 05:31:47
查看原帖
求一种随机生成树算法
685325
zhangzhihao2卷王楼主2023/8/6 20:12

原创一道题,大意如下:一个 nn 个节点的树,要求按照制定顺序依次到达每一个节点,求总路径长度。1≤n≤2×1051\leq n \leq 2\times 10^5

正解是倍增LCA,本来想卡掉普通LCA算法,数据生成的算法大概是先把1到n的排列随机打乱,对于新数列中的每一个点,在前面的所有节点中随机选一个作为父节点。结果普通LCA比倍增跑得还快!!!求一种靠谱的随机生成树算法来卡掉普通LCA。

要题目链接的请私信。

2023/8/6 20:12
加载中...