BZOJ3282 Tree < LCT >

Problem

Tree

Time Limit:
Memory Limit:

Description

给定个点以及每个点的权值，要你处理接下来的个操作。操作有种。操作从到编号。点从到编号。
.后接两个整数，代表询问从到的路径上的点的权值的和。保证到是联通的。
.后接两个整数，代表连接到，若x到y已经联通则无需连接。
.后接两个整数，代表删除边，不保证边存在。
.后接两个整数，代表将点上的权值变成。

Input

第行两个整数，分别为和，代表点数和操作数。
第行到第行，每行一个整数，整数在内，代表每个点的权值。
第行到第行，每行三个整数，分别代表操作类型和操作所需的量。

Output

对于每一个号操作，你须输出到的路径上点权的和。

Sample Input

Sample Output

1
2

3
1

Hint

标签：LCT

Solution

板子题
人生中的第一道
用了没带保护指针的，有几个细节挺坑

Code

#include <bits/stdc++.h>
#define MAX_N 300000
#define INF 0x7f7f7f7f
#define flag (!tar(cur->fa->fa)&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;	int val, sum;	bool rev;
    void updata() {sum = val^(s[0]?s[0]->sum:0)^(s[1]?s[1]->sum:0);}
    void downtag() {
        if (fa && (fa->s[0] == this || fa->s[1] == this)) fa->downtag();
        if (rev && s[0]) swap(s[0]->s[0], s[0]->s[1]), s[0]->rev ^= 1;
        if (rev && s[1]) swap(s[1]->s[0], s[1]->s[1]), s[1]->rev ^= 1;
        rev = false;
    }
} *tr[MAX_N+5];
struct LinkCutTree {
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = v->sum = _val, v->rev = 0;
        return v;
    }
    SplayNode* get_rt(SplayNode* v) {for (; v->fa; v = v->fa) ;	return v;}
    bool tar(SplayNode* v) {return (v&&v->fa==NULL)||(v&&v->fa->s[0]!=v&&v->fa->s[1]!=v);}
    LinkCutTree(int n) {for (int i=1,_val;i<=n;i++) scanf("%d", &_val), tr[i]=newnode(_val);}
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa && !tar(f)) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur) {
        cur->downtag();
        while (!tar(cur) && !tar(cur->fa)) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (!tar(cur) && tar(cur->fa))
            rotate(cur, cur->fa->s[0] == cur);
        cur->updata();
    }
    void access(SplayNode* cur) {
        for (SplayNode* cpy = NULL; cur; cpy = cur, cur = cur->fa)
            splay(cur), cur->s[1] = cpy, cur->updata();
    }
    void mroot(SplayNode* v) {
        access(v), splay(v);
        swap(v->s[0], v->s[1]), v->rev ^= 1;
    }
    void link(SplayNode* u, SplayNode* v) {
        if (get_rt(u) == get_rt(v)) return;
        mroot(u), u->fa = v;
    }
    void cut(SplayNode* u, SplayNode* v) {
        if (u == v || get_rt(u) != get_rt(v)) return;
        mroot(u), access(v), splay(v);
        if (v->s[0] == u) u->fa = v->s[0] = NULL, v->updata();
    }
    void modify(SplayNode* v, int _val) {
        splay(v), v->val = _val, v->updata();
    }
    int query(SplayNode* u, SplayNode* v) {
        mroot(u), access(v), splay(v);
        return v->sum;
    }
};
int main() {
    int n, m;	scanf("%d%d", &n, &m);
    LinkCutTree LCT(n);
    while (m--) {
        int opt, x, y;	scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0) printf("%d\n", LCT.query(tr[x], tr[y]));
        if (opt == 1) LCT.link(tr[x], tr[y]);
        if (opt == 2) LCT.cut(tr[x], tr[y]);
        if (opt == 3) LCT.modify(tr[x], y);
    }
    return 0;
}