「Template」Link Cut Tree

P3690

#include 
#include 

using namespace std;

#define LL long long
#define rep(i, j, k) for(int i = (j); i <= (k); i ++)
#define per(i, j, k) for(int i = (j); i >= (k); i --)

const int Maxn = 1e5;

struct Link_Cut_Tree {    
    struct Node {
        int rev;
        int sum, val;
        int fa, ch[2];
    } spl[Maxn + 5];

    #define fa(x) spl[x].fa
    #define sum(x) spl[x].sum
    #define val(x) spl[x].val
    #define rev(x) spl[x].rev
    #define son(x, d) spl[x].ch[d]

    void Pushup (int p) {
        sum (p) = sum (son (p, 0)) ^ (sum (son (p, 1))) ^ val (p);
    }
    void Flip (int p) { //第一种写法。。
        rev (p) ^= 1;
        swap (son (p, 0), son (p, 1));
    }
    void Pushdown (int p) {
        if (rev (p)) {
            rev (p) = 0;
            if (son (p, 0)) Flip (son (p, 0));
            if (son (p, 1)) Flip (son (p, 1));
        }
    }
    bool Isroot (int p) {
        return !fa (p) || (son (fa (p), 0) ^ p) && (son (fa (p), 1) ^ p);
    }
    bool Dir (int p) {
        return son (fa (p), 1) == p;
    }
    void Connect (int fa, int x, int d) {
        son (fa, d) = x, fa (x) = fa;
    }
    void Rotate (int x) {
        int y = fa (x), z = fa (y);
        int k1 = Dir (x), k2 = Dir (y);
        if (!Isroot (y)) son (z, k2) = x;
        fa (x) = z;
        Connect (y, son (x, k1 ^ 1), k1);
        Connect (x, y, k1 ^ 1);
        Pushup (y), Pushup (x);
    }
    void Push (int x) {
        if (!Isroot (x)) Push (fa (x));
        Pushdown (x);
    }
    void Splay (int p) {
        Push (p);
        while (!Isroot (p)) {
            int fa = spl[p].fa;
            if (!Isroot (fa)) {
                (Dir (fa) ^ Dir (p)) ? Rotate (p) : Rotate (fa);
            }
            Rotate (p);
        }
        Pushup (p);
    }
    void Access (int x) {
        for (int y = x, x = 0; y != 0; x = y, y = spl[y].fa) {
            Splay (y);
            son (y, 1) = x;
            Pushup (y);
        }
    } 
    int Find_Root (int p) {
        Access (p), Splay (p), Pushdown (p);
        while (son (p, 0)) p = son (p, 0), Pushdown (p);
        Splay (p);
        return p;
    }
    void Make_Root (int p) {
        Access (p), Splay (p), Flip (p);
    }
    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 || son (y, 0) || fa (y) != x) return;
        fa (y) = 0, son (x, 1) = 0;
        Pushup (x);
    }
} lct;

int n, m;

int main () {
    scanf ("%d %d", &n, &m);

    rep (i, 1, n) {
        scanf ("%d", &lct.spl[i].val);
        lct.spl[i].sum = lct.spl[i].val;
    }

    rep (i, 1, m) {
        int op, x, y;
        scanf ("%d %d %d", &op, &x, &y);
        switch (op) {
            case 0 : {
                lct.Make_Root (x);
                lct.Access (y);
                lct.Splay (y);
                printf ("%d\n", lct.spl[y].sum);
                break;
            }
            case 1 : { lct.Link (x, y); break; }
            case 2 : { lct.Cut (x, y); break; }
            case 3 : {
                lct.Splay (x);
                lct.spl[x].val = y;
                break;
            }
        }
    }
    return 0;
}

#include 
#include 

using namespace std;

#define LL long long
#define rep(i, j, k) for(int i = (j); i <= (k); i ++)
#define per(i, j, k) for(int i = (j); i >= (k); i --)

const int Maxn = 1e5;

struct Link_Cut_Tree {    
    struct Node {
        int rev;
        int sum, val;
        int fa, ch[2];
    } spl[Maxn + 5];

    #define fa(x) spl[x].fa
    #define sum(x) spl[x].sum
    #define val(x) spl[x].val
    #define rev(x) spl[x].rev
    #define son(x, d) spl[x].ch[d]

    void Pushdown (int p) {
        if (rev (p)) {
            rev (p) = 0;
            swap (son (p, 0), son (p, 1));
            rev (son (p, 0)) ^= 1;
            rev (son (p, 1)) ^= 1;
        }
    }
    void Pushup (int p) {
        Pushdown (son (p, 0));
        Pushdown (son (p, 1));
//此题可以不写上面两句，但如果 pushup 时，与左右儿子的顺序有关就一定要写。
        sum (p) = sum (son (p, 0)) ^ (sum (son (p, 1))) ^ val (p);
    }
    bool Isroot (int p) {
        return !fa (p) || (son (fa (p), 0) ^ p) && (son (fa (p), 1) ^ p);
    }
    bool Dir (int p) {
        return son (fa (p), 1) == p;
    }
    void Connect (int fa, int x, int d) {
        son (fa, d) = x, fa (x) = fa;
    }
    void Rotate (int x) {
        int y = fa (x), z = fa (y);
        int k1 = Dir (x), k2 = Dir (y);
        if (!Isroot (y)) son (z, k2) = x;
        fa (x) = z;
        Connect (y, son (x, k1 ^ 1), k1);
        Connect (x, y, k1 ^ 1);
        Pushup (y), Pushup (x);
    }
    void Push (int x) {
        if (!Isroot (x)) Push (fa (x));
        Pushdown (x);
    }
    void Splay (int p) {
        Push (p);
        while (!Isroot (p)) {
            int fa = spl[p].fa;
            int gfa = spl[fa].fa;
            if (!Isroot (fa)) {
                (Dir (fa) ^ Dir (p)) ? Rotate (p) : Rotate (fa);
            }
            Rotate (p);
        }
        Pushup (p);
    }
    void Access (int x) {
        for (int y = x, x = 0; y != 0; x = y, y = spl[y].fa) {
            Splay (y);
            son (y, 1) = x;
            Pushup (y);
        }
    } 
    int Find_Root (int p) {
        Access (p), Splay (p), Pushdown (p);
        while (son (p, 0)) p = son (p, 0), Pushdown (p);
        Splay (p);
        return p;
    }
    void Make_Root (int p) {
        Access (p), Splay (p), rev (p) ^= 1;
    }
    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 || son (y, 0) || fa (y) != x) return;
        fa (y) = 0, son (x, 1) = 0;
        Pushup (x);
    }

    #undef fa(x)
    #undef sum(x)
    #undef val(x)
    #undef rev(x)
    #undef son(x, d)
} lct;

int n, m;

int main () {
    scanf ("%d %d", &n, &m);

    rep (i, 1, n) {
        scanf ("%d", &lct.spl[i].val);
        lct.spl[i].sum = lct.spl[i].val;
    }

    rep (i, 1, m) {
        int op, x, y;
        scanf ("%d %d %d", &op, &x, &y);
        switch (op) {
            case 0 : {
                lct.Make_Root (x);
                lct.Access (y);
                lct.Splay (y);
                printf ("%d\n", lct.spl[y].sum);
                break;
            }
            case 1 : { lct.Link (x, y); break; }
            case 2 : { lct.Cut (x, y); break; }
            case 3 : {
                lct.Splay (x);
                lct.spl[x].val = y;
                // lct.Pushup (x);
                break;
            }
        }
    }
    return 0;
}