貌似是因为路径压缩改变了并查集的结构
by littlefrog @ 2021-05-04 10:51:02
@[Noir_](/user/100743) 建议去掉路径压缩 $fa[x] = x$
by littlefrog @ 2021-05-04 10:51:39
@[littlefrog](/user/175567) 为什么路径压缩会改变并查集的结构?
by Noir_ @ 2021-05-04 10:55:29
@[Noir_](/user/100743) https://oi-wiki.org/ds/dsu/
by nvme0n1p @ 2021-05-04 10:57:19
@[Noir_](/user/100743) 你说为什么路径压缩会改变并查集的结构
by Arkadyevna @ 2021-05-04 10:57:50
@[Arkadyevna](/user/363937) 好的我知道了,是我孤陋寡闻了,抱歉
by Noir_ @ 2021-05-04 10:58:53
不过这不是Splay吗
by Arkadyevna @ 2021-05-04 11:00:53
旋转的时候会改变树的结构吧
by Ender32k @ 2021-05-04 11:03:56
@[Arkadyevna](/user/363937) 就是才开始学splay所以什么都没搞懂。。。
by Noir_ @ 2021-05-04 11:06:50
@[Ender_32k](/user/306573) 不用了,谢谢我找到错了
```cpp
inline void splay(int x){
for(int f=fa[x];f;rotate(x)){
f=fa[x];
if(f==0) break;
if(fa[f]){
if(get_son(x)==get_son(f)) rotate(f);
else rotate(x);
}
}
root=x;
}
```
改成这样就行了
by Noir_ @ 2021-05-04 11:07:52