转移自老blog

bzoj3123

链接

题意

        1.求森林任意路径第k大,2.森林合并,森林点个数1e5

题解

        在主席树上加上启发式合并即可,合并的时候更新lca的倍增数组,启发式生成新的主席树,可以证明合并的均摊时间复杂度为lg级别