← all categories

Link Cut Tree baedc2bd

Link-cut tree over a fixed set of n labeled nodes (1-indexed; node 0 is a null placeholder). Supports link, cut, findRoot, and path aggregate (default sum) between two nodes via makeRoot + access. To reset between test cases, construct a new LinkCutTree(n). T needs operator+ and a default-constructed zero. Multi-page exception to the line budget.

Time: O(\log n) amortized per operation. tested

content/data-structures/link-cut-tree.h

template <typename T>
struct LinkCutTree {
    struct Node {
        int ch[2] = {0, 0}, fa = 0;
        bool rev = false;
        T val = T(), sum = T();
    };
    vector<Node> t;

    LinkCutTree(int n) { t.assign(n + 1, Node()); }

    bool isRoot(int x) { int f = t[x].fa; return f == 0 || (t[f].ch[0] != x && t[f].ch[1] != x); }

    void pushUp(int x) {
        t[x].sum = t[x].val + (t[x].ch[0] ? t[t[x].ch[0]].sum : T()) + (t[x].ch[1] ? t[t[x].ch[1]].sum : T());
    }

    void pushRev(int x) {
        if (!x) return;
        swap(t[x].ch[0], t[x].ch[1]);
        t[x].rev ^= 1;
    }

    void pushDown(int x) {
        if (t[x].rev) {
            pushRev(t[x].ch[0]);
            pushRev(t[x].ch[1]);
            t[x].rev = false;
        }
    }

    void pushDownAll(int x) {  // propagate lazy tags from the splay-tree root down to x
        if (!isRoot(x)) pushDownAll(t[x].fa);
        pushDown(x);
    }

    void rotate(int x) {
        int y = t[x].fa, z = t[y].fa;
        int dx = (t[y].ch[1] == x), dy = (t[z].ch[1] == y);
        if (!isRoot(y)) t[z].ch[dy] = x;
        t[x].fa = z;
        t[y].ch[dx] = t[x].ch[dx ^ 1];
        if (t[x].ch[dx ^ 1]) t[t[x].ch[dx ^ 1]].fa = y;
        t[x].ch[dx ^ 1] = y;
        t[y].fa = x;
        pushUp(y); pushUp(x);
    }

    void splay(int x) {
        pushDownAll(x);
        while (!isRoot(x)) {
            int y = t[x].fa;
            if (!isRoot(y)) {
                if ((t[t[y].fa].ch[0] == y) ^ (t[y].ch[0] == x)) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
        pushUp(x);
    }

    int access(int x) {  // makes the root-to-x path the preferred path; splays x to the top
        int last = 0;
        for (int y = x; y; y = t[y].fa) {
            splay(y);
            t[y].ch[1] = last;
            pushUp(y);
            last = y;
        }
        splay(x);
        return last;
    }

    void makeRoot(int x) { access(x); pushRev(x); }

    int findRoot(int x) {
        access(x);
        while (t[x].ch[0]) { pushDown(x); x = t[x].ch[0]; }
        splay(x);
        return x;
    }

    void link(int x, int y) {  // requires x, y in different trees
        makeRoot(x);
        if (findRoot(y) != x) t[x].fa = y;
    }

    void cut(int x, int y) {  // requires the edge (x, y) to exist
        makeRoot(x);
        access(y);
        if (t[y].ch[0] == x && t[x].fa == y && t[x].ch[1] == 0) {
            t[y].ch[0] = 0;
            t[x].fa = 0;
            pushUp(y);
        }
    }

    T pathSum(int x, int y) {  // requires x, y in the same tree
        makeRoot(x);
        access(y);
        return t[y].sum;
    }

    void setVal(int x, T v) {
        access(x);
        t[x].val = v;
        pushUp(x);
    }
};