原创一道题,大意如下:一个 nnn 个节点的树,要求按照制定顺序依次到达每一个节点,求总路径长度。1≤n≤2×1051\leq n \leq 2\times 10^51≤n≤2×105
正解是倍增LCA,本来想卡掉普通LCA算法,数据生成的算法大概是先把1到n的排列随机打乱,对于新数列中的每一个点,在前面的所有节点中随机选一个作为父节点。结果普通LCA比倍增跑得还快!!!求一种靠谱的随机生成树算法来卡掉普通LCA。
要题目链接的请私信。