LCT

\(LCT\)Full name\(Link\) \(Cut\) \(Tree\)that can solve the dynamic tree problem.

Dynamic trees (LCT)

\(isroot\) manipulate

If a point is not a root, consider that it is neither the left nor the right son of the father. Code:

bool isroot(int x){
    return tr[tr[x].p].s[0]!=x&&tr[tr[x].p].s[1]!=x;
}

\(rotate\) manipulate

suppose that...\(x\) because of\(7\)，\(y\) because of\(3\)，\(z\) because of\(1\)That is to say, it's important to put\(7\) Spin up. If I thought about spinning up, I would turn my father underneath me. So I disconnected the edge with my father and connected the edge with my grandfather.

Next realizing that his father was missing a son, he put his ownThe son on the other side.to the father, and at the same time break off the side to which he had attached himself.

Finally we just need to link\(x\) cap (a poem)\(y\)Only this time.\(x\) It's the father.

Code:

void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1];
    tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y;
    tr[y].p=x;
    pushup(y);
    pushup(x);
}

\(splay\) manipulate

Let's categorize the discussion first and see\(x,y,z\) In terms of not being in a straight line, you can look at the graph:

It is easy to see that if in a straight line, the first turn\(y\)And then turn around.\(x\)Otherwise, two turns in a row.\(x\). This continues until\(x\) Was turned to heel.

But before we do the rotation, we have to make the path to turn up the\(pushdown\). Code:

void splay(int x){
    int top=0,r=x;
    stk[++top]=r;
    while(!isroot(r))stk[++top]=r=tr[r].p;
    while(top)pushdown(stk[top--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if((tr[y].s[1]==x)^(tr[z].s[1]==y))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}