是 $\alpha$ 吧，不过一般经常把并查集看成 $O(1)$ 的，所以这么说
by rui_er @ 2024-01-19 23:52:34
反阿克曼函数好像可以忽略为一个常数吧，我记得《算法竞赛进阶指南》上面写的 $2$ 的多少次方的多少次发都小于等于 $5$。
by cjh20090318 @ 2024-01-20 00:00:27
其实问题是用 tarjan LCA 做链信息查询 [现在找到了这个](https://return20071007.blog.uoj.ac/blog/7456)，这样信息合并次数的复杂度仍然是 $n\log n$ 的。
by Rainbow_qwq @ 2024-01-20 00:21:28
请问为啥不是线性啊？能不能提供一个 $\Omega(n\alpha(n))$ 的证明？没想明白。
by Eznibuil @ 2024-01-20 00:40:16
@[Eznibuil](/user/335096) 没有理由是线性，不如说为什么和普通并查集有区别。
by UnyieldingTrilobite @ 2024-01-20 06:22:23
@[cjh20090318](/user/577880) 3。
你那个是 $\log^*$。
by UnyieldingTrilobite @ 2024-01-20 06:23:05
这个事情可以去看 OI-wiki，几年前修正过。原论文实际上指出可以线性但需要使用一种特殊的并查集（类似四毛子，这个技巧倒是很多地方都有介绍），但不知道被谁最开始曲解成了性质特殊导致并查集线性……
by UnyieldingTrilobite @ 2024-01-20 06:24:16
另外可以按秩合并，把并查集节点和它所对应的树节点分离就行，具体就是对每个并查集节点额外维护一个到树节点的映射，然后按秩合并中的交换操作就平凡了。
by UnyieldingTrilobite @ 2024-01-20 06:25:53
我们老师说线性（
by AAA404 @ 2024-01-20 06:41:46
我一直当线性算的（）
by cmaths @ 2024-01-20 06:54:13