BZOJ原题地址

洛谷原题地址

思路

两个操作,求路径上第k大,还要连边。
前者让我们想到主席树,后者又是典型的LCT。
但是LCT我不会啊,所以我写了一发主席树。
对于查询,LCA一下,差分即可。
对于连边,那就。。。连边吧。因为保证连边之后依然是森林,就可以启发式合并,并查集维护。
注意这道题的输入有一个很坑的地方。第一行输入testcase,用处是什么呢?真的只是标明 testcase 而不是多组数据。

代码