MinDeltaTree

#include <cstdio>

#include <algorithm>

using namespace std;

struct Data {
    int v, id;

    bool operator<(const Data& x) const {
        return v < x.v;
    }
};

const int N = 250010;

struct LinkCutTree {
    struct Node {
        bool rev;
        Data v, myn;
        union {
            struct {
                Node *ls, *rs;
            };
            Node* ch[2];
        };
        Node *prt, *path;

        bool relation() const {
            return this == prt->rs;
        }

        void pushDown() {
            if (rev) {
                rev = false;
                swap(ls, rs);
                if (ls)
                    ls->rev = !ls->rev;
                if (rs)
                    rs->rev = !rs->rev;
            }
        }

        void update() {
            myn = v;
            if (ls)
                myn = min(myn, ls->myn);
            if (rs)
                myn = min(myn, rs->myn);
        }

        void rotate() {
            if (prt->prt)
                prt->prt->pushDown();
            prt->pushDown();
            pushDown();
            path = prt->path;
            prt->path = NULL;
            Node* p = prt;
            bool f = relation();
            if (p->prt)
                p->prt->ch[p->relation()] = this;
            prt = p->prt;
            p->ch[f] = ch[!f];
            if (ch[!f])
                ch[!f]->prt = p;
            ch[!f] = p;
            p->prt = this;
            p->update();
            update();
        }

        void splay() {
            while (prt) {
                if (!prt->prt)
                    return rotate();
                prt->prt->pushDown();
                prt->pushDown();
                if (relation() == prt->relation()) {
                    prt->rotate();
                    rotate();
                } else {
                    rotate();
                    rotate();
                }
            }
        }

        void expose() {
            splay();
            pushDown();
            if (rs) {
                rs->path = this;
                rs->prt = NULL;
                rs = NULL;
                update();
            }
        }

        bool splice() {
            splay();
            if (!path)
                return false;
            path->expose();
            path->rs = this;
            prt = path;
            path = NULL;
            prt->update();
            return true;
        }

        void access() {
            expose();
            while (splice());
        }

        void evert() {
            access();
            splay();
            rev = !rev;
        }
    };

    Node ver[N];

    void link(int u, int v) {
        ver[u].evert();
        ver[u].path = ver + v;
    }

    void cut(int u, int v) {
        ver[u].evert();
        ver[v].access();
        ver[v].splay();
        ver[v].pushDown();
        ver[v].ls = NULL;
        ver[v].update();
        ver[u].prt = NULL;
    }

    Data query(int u, int v) {
        ver[u].evert();
        ver[v].access();
        ver[v].splay();
        return ver[v].myn;
    }
};

int main() {
    return 0;
}