LCT学习笔记

spdarkle · 2021-08-22 11:27:34 · 个人记录

换根就简单得多了，将x和原树根用access操作打通一条实链，然后将x旋转为伸展树的根，因为树根深度最小，而原来的x因为在链底，深度最大，x为根就没有右儿子，直接交换左右儿子，这样就变成了没有左儿子，他的深度最小。

inline void makeroot(int x) {
        access(x);
        splay(x);
        lz[x] ^= 1;
    }

查找一个点的根：

直接找Splay树上深度最小点即可

inline int findroot(int x) {
        access(x), splay(x);
        while (ch[x][0])x = ch[x][0];
        return x;
    }

打通x,y的连接：

先将x变为根，然后y打通和根的连接就行

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

删边：

打通x和y的连接，如果他们之间只有一条边，那么直接置空儿子和父亲

因为split的时候y被旋转为了根，所以如果只有一条边的话x应为叶子节点，y的左儿子该为x

这时候直接将y的左儿子变成空，左儿子父亲也变成空

inline void cut(int x, int y) {
        split(x, y);
        if (ch[y][0] != x || ch[x][1])return;
        ch[y][0] = f[ch[y][0]] = 0;
        pushup(y);
    }

加边：

更简单了，直接将x变成根，然后把x的父亲变成y即可，记得判联通性，就是找两个点所在的原树的根

inline void link(int x,int y) {
        makeroot(x);
        f[x] = y;
    }

下面放上该题的AC Code

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
struct Link_Cut_Tree{
    stack<int>hs;
#define lc ch[s][0]
#define rc ch[s][1]
    int sum[10005], ch[10005][2], val[100004], a[100004], f[100004], lz[100005], cnt;
    inline void pushup(int s) {
        sum[s] = sum[ch[s][1]] ^ sum[ch[s][0]] ^ a[s];
    }
    inline void pushdown(int s) {
        if (lz[s]) {
            lz[s] = 0;
            lz[lc] ^= 1, lz[rc] ^= 1;
            swap(lc, rc);
        }
    }
    inline bool isroot(int x) {
        return ch[f[x]][0] != x && ch[f[x]][1] != x;
    }
    inline void rotate(int s) {
        int y = f[s];
        int z = f[y];
        int k = ch[y][0] == s;
        if (!isroot(y)) {
            ch[z][ch[z][1] == y] = s;
        }
        f[s] = z;
        f[y] = s;
        f[ch[s][k]] = y;
        ch[y][!k] = ch[s][k];
        ch[s][k] = y;
        pushup(y), pushup(s);
    }
    inline void splay(int x) {
        while (hs.size())hs.pop();
        hs.push(x);
        for (int i = x; !isroot(i); i = f[i]) {
            hs.push(f[i]);
        }
        while (hs.size()) {
            pushdown(hs.top());
            hs.pop();
        }
        while (!isroot(x)) {
            int y = f[x], z = f[y];
            if (!isroot(y)) {
                (ch[z][1] == y) ^ (ch[y][1] == x) ? rotate(x) : rotate(y);
            }
            rotate(x);
        }
    }
    inline void access(int x) {
        for (int y = 0;x; y = x, x = f[x]) {
            splay(x), ch[x][1] = y, pushup(x);
        }
    }
    inline void makeroot(int x) {
        access(x);
        splay(x);
        lz[x] ^= 1;
    }
    inline int findroot(int x) {
        access(x), splay(x);
        while (ch[x][0])x = ch[x][0];
        return x;
    }
    inline void split(int x, int y) {
        makeroot(x);
        access(y);
        splay(y);
    }
    inline void cut(int x, int y) {
        split(x, y);
        if (ch[y][0] != x || ch[x][1])return;
        ch[y][0] = f[ch[y][0]] = 0;
        pushup(y);
    }
    inline void link(int x,int y) {
        makeroot(x);
        f[x] = y;
    }
}LCT;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> LCT.a[i];
    }
    while (m--) {
        int x, y, z, s;
        cin >> x >> y >> z;
        if (x == 0) {
            LCT.split(y, z);
            printf("%d\n", LCT.sum[z]);
        }
        else if (x == 1) {
            if (LCT.findroot(z) == LCT.findroot(y)) {
                continue;
            }
            LCT.link(y, z);
        }
        else if (x == 2) {
            if (LCT.findroot(z) == LCT.findroot(y)) {
                LCT.cut(y, z);
            }
        }
        else {
            LCT.splay(y);
            LCT.a[y] = z;
        }
    }
    return 0;
}

至于LCT维护最近公共祖先的话先access一遍，并把路径打上标记，然后再access另一个点，遇到的第一个有标记的就是他们的最近公共祖先。

至于LCT维护边权，就不能使用树剖的方法了，对每条边新建一个点，向他的两个端点连边，点权为边权。

LCT维护最小生成树：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define R register int
#define I inline void
#define lc c[x][0]
#define rc c[x][1]
using namespace std;
const int N = 1e6 + 10;
int c[N][2], st[N], f[N], mx[N], fa[N], val[N], r[N], n, m, Q;
inline int in() {
    int w = 0, x = 0; char c = 0;
    while (c < '0' || c>'9') w |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return w ? -x : x;
}
inline bool nroot(R x) {
    return c[f[x]][0] == x || c[f[x]][1] == x;
}
I pushup(R x) {
    mx[x] = x;
    if (val[mx[lc]] > val[mx[x]]) mx[x] = mx[lc];
    if (val[mx[rc]] > val[mx[x]]) mx[x] = mx[rc];
}
I pushr(R x) {
    swap(lc, rc); r[x] ^= 1;
}
I pushdown(R x) {
    if (r[x]) {
        if (lc) pushr(lc);
        if (rc) pushr(rc);
        r[x] = 0;
    }
}
I rotate(R x) {
    R y = f[x], z = f[y], k = c[y][1] == x, w = c[x][k ^ 1];
    if (nroot(y)) c[z][c[z][1] == y] = x;
    c[x][k ^ 1] = y; c[y][k] = w;
    if (w) f[w] = y; f[y] = x; f[x] = z;
    pushup(y);
}
I splay(R x) {
    R y = x, z = 0;
    st[++z] = y;
    while (nroot(y)) st[++z] = y = f[y];
    while (z) pushdown(st[z--]);
    while (nroot(x)) {
        y = f[x], z = f[y];
        if (nroot(y)) rotate((c[y][1] == x) ^ (c[z][1] == y) ? x : y);
        rotate(x);
    }
    pushup(x);
}
I access(R x) {
    for (R y = 0; x; x = f[y = x])
        splay(x), rc = y, pushup(x);
}
I makeroot(R x) {
    access(x); splay(x);
    pushr(x);
}
inline int findroot(R x) {
    access(x); splay(x);
    while (lc) pushdown(x), x = lc;
    splay(x);
    return x;
}
I split(R x, R y) {
    makeroot(x);
    access(y); splay(y);
}
I link(R x, R y) {
    makeroot(x);
    if (findroot(y) != x) f[x] = y;
}
I cut(R x, R y) {
    makeroot(x);
    if (findroot(y) == x && f[y] == x && !c[y][0]) {
        c[x][1] = f[y] = 0;
        pushup(x);
    }
}
int query(int u, int v) {
    split(u, v); return mx[v];
}
struct edge {
    int u, v, w, id, d;
    bool operator < (const edge& a)const {
        if (w == a.w) return id < a.id;
        return w < a.w;
    }
}e[N];
bool cmp(edge a, edge b) {
    return a.u < b.u || (a.u == b.u && a.v < b.v);
}
struct que {
    int u, v, id, op, ans;
}q[N];
int get(R x) {
    return x == fa[x] ? x : fa[x] = get(fa[x]);
}
inline int find(R u, R v) {
    int l = 1, r = m;
    while (l <= r) {
        int mid = l + r >> 1;
        if (e[mid].u < u || (e[mid].u == u && e[mid].v < v)) l = mid + 1;
        else if (e[mid].u == u && e[mid].v == v) return mid;
        else r = mid - 1;
    }
}
int main() {
    n = in(), m = in(), Q = in();
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        e[i].u = in(), e[i].v = in(), e[i].w = in();
        if (e[i].u > e[i].v) swap(e[i].u, e[i].v);
    }
    //  printf("1\n");
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= m; i++) {
        val[i + n] = e[i].w;
        mx[i + n] = i + n;
        e[i].id = i;
    }
    //printf("2\n");
    sort(e + 1, e + 1 + m, cmp);
    for (int i = 1; i <= Q; i++) {
        q[i].op = in(), q[i].u = in(), q[i].v = in();
        if (q[i].op == 2) {
            if (q[i].u > q[i].v)swap(q[i].u, q[i].v);
            int t = find(q[i].u, q[i].v);
            q[i].id = e[t].id; e[t].d = 1;
        }
    }
    //printf("3\n");
    sort(e + 1, e + 1 + m);
    int tot = 0;
    for (int i = 1; i <= m; i++) {
        if (!e[i].d) {
            int x = get(e[i].u), y = get(e[i].v);
            if (x != y) {
                tot++;
                fa[x] = y;
                link(e[i].u, i + n); link(e[i].v, i + n);
                if (tot == n - 1) break;
            }
        }
    }
    //printf("4\n");
    for (int i = Q; i >= 1; i--) {
        if (q[i].op == 1) {
            q[i].ans = val[query(q[i].u, q[i].v)];
        }
        else {
            int t = query(q[i].u, q[i].v), k = q[i].id;
            if (e[k].w < val[t]) {
                cut(e[t - n].u, t); cut(e[t - n].v, t);
                link(q[i].u, k + n); link(q[i].v, k + n);
            }
        }
    }
    for (int i = 1; i <= Q; i++) if (q[i].op == 1) printf("%d\n", q[i].ans);
    return 0;
}

以WC2006水管局长为例