[数据结构与算法]LCT求LCA（乱搞，记录）

P3379 【模板】最近公共祖先（LCA）
拿洛谷模板试了试，o2水过了70分嚯嚯嚯，可惜了

// luogu-judger-enable-o2
/**
 * 动态LCA
 * 
 * 先将树根makeroot
 * 
 * 每次求x和y的公共祖先时
 * 
 * 先access(x),将x和s之间建一个实链,使他们在一个splay里.
 * 
 * 所以 y 到 LCA 一定是一条虚边，故在 access(y) 的时候每次记录跳过的虚边是跳到了谁那里
 * 
 * 然后将最后一次跑虚边的点(父亲)返回
 * */

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

const int mod = 51061;
const int N = 500009;
typedef long long ll;

int n, st[N];
class LCT {
public:
    struct vec {
        int son[2], f;
        bool tag;
        ll sz;
        vec()
        {
            sz = 1;
        }
    } p[N];

    inline bool isroot(int x)
    { //好像Daaddo都写的是isroot
        return p[p[x].f].son[0] == x || p[p[x].f].son[1] == x;
    }
    inline void pushup(int x)
    {
        p[x].sz = p[p[x].son[0]].sz + p[p[x].son[1]].sz + 1;
    }
    inline void pushr(int x)
    { //翻转
        swap(p[x].son[0], p[x].son[1]);
        p[x].tag ^= 1;
    }
    inline void pushdown(int x)
    {
        if (p[x].tag) {
            if (p[x].son[0])
                pushr(p[x].son[0]);
            if (p[x].son[1])
                pushr(p[x].son[1]);
            p[x].tag = 0;
        }
    }
    inline void rotate(int x)
    {
        int y = p[x].f, z = p[y].f, k = p[y].son[1] == x, w = p[x].son[!k];
        if (isroot(y))
            p[z].son[p[z].son[1] == y] = x;
        p[x].son[!k] = y;
        p[y].son[k] = w;
        if (w)
            p[w].f = y;
        p[y].f = x;
        p[x].f = z;
        pushup(y);
    }
    inline void splay(int x)
    {
        int y = x, z = 0;
        st[++z] = y;
        while (isroot(y))
            st[++z] = y = p[y].f;
        while (z)
            pushdown(st[z--]);
        while (isroot(x)) {
            y = p[x].f;
            z = p[y].f;
            if (isroot(y))
                rotate((p[y].son[0] == x) ^ (p[z].son[0] == y) ? x : y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x)
    {
        for (int y = 0; x; x = p[y = x].f)
            splay(x), p[x].son[1] = y, pushup(x);
    }
    inline void makeroot(int x)
    {
        access(x);
        splay(x);
        pushr(x);
    }
    inline void split(int x, int y)
    {
        makeroot(x);
        access(y);
        splay(y);
    }
    inline void link(int x, int y)
    {
        makeroot(x);
        p[x].f = y;
    }
    inline void cut(int x, int y)
    {
        split(x, y);
        p[x].f = p[y].son[0] = 0;
    }
    inline int LCA(int u, int v)
    {
        access(u);
        int ans = v;
        for (int i = 0; v; ans = i = v, v = p[i].f) {
            splay(v), p[v].son[1] = i;
        }
        return ans;
    }
} root;

int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    int u, v;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        root.link(u, v);
    }
    root.makeroot(s);
    while (m--) {
        cin >> u >> v;
        printf("%d\n", root.LCA(u, v));
    }

    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖