LCT 第一题

P3690 【模板】Link Cut Tree （动态树）

LCT第一题，模板来自题解的博客，也是我学会LCT看的博客ORZ。

存一下好找。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 10;
typedef long long LL;

#define fa(x) T[x].f
#define ls(x) T[x].ch[0]
#define rs(x) T[x].ch[1]

int v[MAXN];

struct node {
    int f, ch[2], s;

    bool r;
} T[MAXN];

inline int read() {
    char c = getchar();int x = 0,f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - '0', c = getchar(); }
    return x * f;
}

int ident(int x) {
    return T[fa(x)].ch[0] == x ? 0 : 1;
}

int connect(int x, int fa, int how) {
    T[x].f = fa;
    T[fa].ch[how] = x;
}

inline bool isRoot(int x) { //若为splay中的根则返回1 否则返回0
    return ls( fa(x) ) != x && rs( fa(x) ) != x;
    //用到了两个性质
    //1.若x与fa(x)之间的边是虚边，那么它的父亲的孩子中不会有他（不在同一个splay内）
    //2. splay的根节点与其父亲之间的边是虚边
}

void push_up(int x) {
    T[x].s = T[ls(x)].s ^ T[rs(x)].s ^ v[x]; //维护路径上的异或和
}

void push_down(int x) {
    if(T[x].r) {
        swap(ls(x),rs(x));
        T[ls(x)].r ^= 1;
        T[rs(x)].r ^= 1;
        T[x].r = 0;
    }
}

void rotate(int x) {
    int Y = T[x].f, R = T[Y].f, Yson = ident(x), Rson = ident(Y);
    int B = T[x].ch[Yson ^ 1];
    T[x].f = R;
    if(!isRoot(Y)) {
        connect(x, R, Rson);
    }
    connect(B, Y, Yson);
    connect(Y, x, Yson ^ 1);
    push_up(Y); push_up(x);
}

int st[MAXN];

void splay(int x) {
    int y = x, top = 0;
    st[++top] = y;
    while(!isRoot(y)) { st[++top] = y = fa(y); }
    while(top) { push_down(st[top--]); }
    for(int y = fa(x); !isRoot(x); rotate(x), y = fa(x)) {
        if(!isRoot(y)) {
            rotate( ident(x) == ident(y) ? x : y );
        }
    }
}

void access(int x) {
    for(int y = 0; x; x = fa(y = x)) {
        splay(x), rs(x) = y, push_up(x);
    }
}

void make_root(int x) {
    access(x);
    splay(x);
    T[x].r ^= 1;
    push_down(x);
}

int find_root(int x) {
    access(x); splay(x); push_down(x);
    while(ls(x)) { push_down(x = ls(x)); }
    return x;
}

void split(int x, int y) {
    make_root(x); access(y); splay(y);
}

void link(int x, int y) {
    make_root(x);
    if(find_root(y) != x) {
        fa(x) = y;
    }
}

void cut(int x, int y) {
    make_root(x);
    if(find_root(y) == x && fa(x) == y && ls(y) == x && !rs(x)) {
        fa(x) = T[y].ch[0] = 0;
        push_up(y);
    }
}

int main()
{
    int N = read(), M = read();
    for(int i = 1; i <= N; i++) v[i] = read();
    for(int i = 1; i <= M; i++) {
        int opt = read(), x = read(), y = read();
        if(opt == 0) split(x, y), printf("%d\n",T[y].s);
        else if(opt == 1) link(x, y);
        else if(opt == 2) cut(x, y);
        else if(opt == 3) splay(x), v[x] = y;
    }
    return 0;
}