为什么双旋会错啊

老K @ 2017-07-15 17:30:34

void splay(int x){
    push_tag(x);
    while(fa[x]){
        /*if(fa[fa[x]]){//这是双旋代码，用它会TLE
            if((son[fa[x]][1]==x)==(son[fa[fa[x]]][1]==fa[x])){
                rotate(fa[x]);
                rotate(x);
            }
            else{
                rotate(x);
                rotate(x);
            }
        }
        else{
            rotate(x);
        }*/
        rotate(x);//单旋，可过。
    }
    rot=x;
}

by 老K @ 2017-07-15 17:30:54

求大佬解释下这是为什么

by 老K @ 2017-07-15 17:32:35

完整代码：传送门

by xunzhen @ 2018-01-11 22:02:16

@罗恺 你双旋写得太丑了

by xunzhen @ 2018-01-11 22:04:55

int check(int x){
    return A[A[x].fa].son[1]==x;
}
void splay(int x,int y){
    while (A[x].fa!=y){
        int f=A[x].fa;
        int dx=check(x),df=check(f);
        if (A[f].fa==y) rotate(x);
        else if (dx==df) rotate(f),rotate(x);
        else rotate(x),rotate(x);
    }
    if (!y) root=x;
}