Link cut tree 实现不高效的 LCA

https://www.luogu.org/problemnew/show/P3379

求 a 和 b 的 LCA

考虑先 access(a)，此时 a 和 root 在一条链上，再 access(b) 记录最后一个被 access 遇到的点，即为 LCA

因为LCT常数太大所以要开O2才能过

#include <bits/stdc++.h>

using namespace std;

const int N = 500000 + 10;

int fa[N], ch[N][2], val[N], rev[N], st[N], n, m, root, len;

int isroot(int u) {

    return ch[fa[u]][0] != u && ch[fa[u]][1] != u;

}

int get(int u) {

    return ch[fa[u]][1] == u;

}

void pushdown(int u) {

    if(rev[u]) {

        swap(ch[u][0], ch[u][1]);

        rev[ch[u][0]] ^= 1;

        rev[ch[u][1]] ^= 1;

        rev[u] ^= 1;

    }

}

void rotate(int u) {

    int old = fa[u], oldd = fa[old], k = get(u);

    if(!isroot(old)) ch[oldd][get(old)] = u; fa[u] = oldd;

    fa[ch[u][k ^ 1]] = old; ch[old][k] = ch[u][k ^ 1];

    fa[old] = u; ch[u][k ^ 1] = old;

}

void splay(int u) {

    st[len = 1] = u;

    for(int i = u; !isroot(i); i = fa[i]) st[++len] = fa[i];

    for(int i = len; i >= 1; i--) pushdown(st[i]);

    for(; !isroot(u); rotate(u)) if(!isroot(fa[u])) rotate(get(u) == get(fa[u]) ? fa[u] : u);

}

int access(int u) {

    int tmp;

    for(int i = 0; u; i = u, u = fa[u]) {

        splay(u);

        ch[u][1] = i;

        tmp = u;

    }

    return tmp;

}

void makeroot(int u) {

    access(u);

    splay(u);

    rev[u] ^= 1;

}

void link(int x, int y) {

    makeroot(x);

    fa[x] = y;

}

int main() {

    scanf("%d %d %d", &n, &m, &root);

    for(int i = 1; i < n; i++) {

        int a, b;

        scanf("%d %d", &a, &b);

        link(a, b);

    }

    makeroot(root);

    for(int i = 1; i <= m; i++) {

        int a, b;

        scanf("%d %d", &a, &b);

        access(a); printf("%d\n", access(b));

    }

    return 0;

}

巴特西

Link cut tree 实现不高效的 LCA

最新文章

热门文章