因为 findroot 函数你遍历了左链找根而没有旋转。
by jerry3128 @ 2023-07-01 10:59:56
@[jerry3128](/user/27338) 所以是应该在每次findroot后都splay一遍找到的根是吗？
by xie_lzh @ 2023-07-01 11:08:14
是的，遍历即旋转。
by jerry3128 @ 2023-07-01 11:11:40
@[jerry3128](/user/27338) 谢谢，但是好像不是这里的问题...
我将
```cpp
void splay(int x)
{
update(x);
while(!isroot(x))
{
int y=pos[x].fa;
if(!isroot(y))(gett(x)^gett(y))?rot(y):rot(x);
rot(x);
}
pushup(x);
}
```
改为了
```cpp
void splay(int x)
{
update(x);
while(!isroot(x))
{
int y=pos[x].fa;
if(!isroot(y))(gett(x)==gett(y))?rot(y):rot(x);
rot(x);
}
pushup(x);
}
```
然后就过了。
属于是实现细节问题...
by xie_lzh @ 2023-07-01 11:21:56