线性树上并查集？这不是王相文2023年集训队论文吗。
by zjy2008 @ 2024-01-20 07:30:07
<https://ljt12138.blog.uoj.ac/blog/4874> 这个应该是线性
by jijidawang @ 2024-01-20 07:40:47
要线性得线性树上并查集
by cyffff @ 2024-01-20 08:08:53
可以按秩合并的，楼上说的对。
by 聊机 @ 2024-01-20 08:32:10
@[UnyieldingTrilobite](/user/250637) 我比较好奇这个东西做信息合并的常数是多少，比如可以用来优化建图（一个点向一条链连边）之类的，点数能不能比倍增小。
by Rainbow_qwq @ 2024-01-20 10:14:06
@[Rainbow_qwq](/user/151935) 没有研究过，但是倍增肯定亏吧。
有没有例子。
by UnyieldingTrilobite @ 2024-01-20 11:08:36
@[UnyieldingTrilobite](/user/250637) 维护信息就不行了吧？
by flowerletter @ 2024-01-20 11:15:37
并查集做树链静态半群信息应该只能$O(m \log_{1+\frac{m}{n}} n)$
by flowerletter @ 2024-01-20 11:16:11
@[Rainbow_qwq](/user/151935) 我见过有人用这个！跑的飞快
by flowerletter @ 2024-01-20 11:16:41
@[flowerletter](/user/55650) 维护信息我没搞错的话应该确实没法按秩（
by UnyieldingTrilobite @ 2024-01-20 13:02:25