「SDOI2013」森林-主席树+LCA+启发式合并

小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$。

「AHOI2008」紧急集合-LCA

给出一颗 $n$ 个节点的无权树, $m$ 次询问,每次给出三个点编号为 $a$ , $b$ , $c$ ,询问到这三个点距离最小的点的编号以及其距离和。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×