小Z有一片森林,含有$N$个节点,每个节点上都有一个非负整数作为权值。初始的时候,森林中有$M$条边。
小Z希望执行$T$个操作,操作有两类:
Q x y k
查询点$x$到点$y$路径上所有的权值中,第$k$小的权值是多少。此操作保证点$x$和点$y$连通,同时这两个节点的路径上至少有$k$个点。L x y
在点$x$和点$y$之间连接一条边。保证完成此操作后,仍然是一片森林。
强制在线。
对于所有的数据$n,m,T \leq 8 \times 10^4$。
链接
题解
恶心的大数据结构。
对于合并操作,我们会想到LCT
,而对于查询路径上的第$k$大,又让我们想到主席树。
只能牺牲一种操作。注意到这里没有cut
,所以我们可以通过启发式合并的方式,减少一个$\log$。
用并查集维护森林的大小,每次合并的时候强势暴力dfs修改树上路径主席树,以及求lca
的倍增数组即可。
然后就是常规操作了。
需要用离散化,这里用了$map$。
代码
1 |
|