Link cut tree

linkcut.rs

trait LinkCutOp {
    type T;

    fn pull(_t: &mut LinkCutTree<Self>, _u: usize) {}
    fn push(_t: &mut LinkCutTree<Self>, _u: usize) {}
}

struct LinkCutNode<T> {
    v: T,
    c: [u32; 2],
    p: u32,
}

struct LinkCutTree<Op: LinkCutOp + ?Sized> {
    v: Vec<LinkCutNode<Op::T>>,
}

impl<Op: LinkCutOp> LinkCutTree<Op> {
    fn new() -> Self {
        Self { v: vec![] }
    }

    fn push(&mut self, v: Op::T) -> u32 {
        let i = self.v.len();
        self.v.push(LinkCutNode {
            v,
            c: [u32::MAX; 2],
            p: u32::MAX,
        });
        i as u32
    }

    fn side(&self, n: u32) -> usize {
        let p = self.v[n as usize].p as usize;
        if self.v[p].c[0] == n {
            0
        } else {
            1
        }
    }

    fn is_root(&self, n: u32) -> bool {
        let p = self.v[n as usize].p;
        p == u32::MAX || (self.v[p as usize].c[0] != n && self.v[p as usize].c[1] != n)
    }

    fn attach(&mut self, u: u32, v: u32, i: usize) {
        if v != u32::MAX {
            self.v[v as usize].p = u;
        }
        self.v[u as usize].c[i] = v;
    }

    fn rotate(&mut self, n: u32) {
        let p = self.v[n as usize].p;
        let i = self.side(n);
        if self.is_root(p) {
            self.v[n as usize].p = self.v[p as usize].p;
        } else {
            self.attach(self.v[p as usize].p, n, self.side(p));
        }
        self.attach(p, self.v[n as usize].c[i ^ 1], i);
        self.attach(n, p, i ^ 1);
        Op::pull(self, p as usize);
        Op::pull(self, n as usize);
    }

    fn splay(&mut self, n: u32) {
        while !self.is_root(n) {
            let p = self.v[n as usize].p;
            if !self.is_root(p) {
                Op::push(self, self.v[p as usize].p as usize);
                Op::push(self, p as usize);
                Op::push(self, n as usize);
                if self.side(p) == self.side(n) {
                    self.rotate(p);
                } else {
                    self.rotate(n);
                }
            } else {
                Op::push(self, p as usize);
                Op::push(self, n as usize);
            }
            self.rotate(n);
        }
        Op::push(self, n as usize);
    }

    fn find<F>(&mut self, mut n: u32, mut f: F) -> u32
    where
        F: FnMut(&Self, usize) -> usize,
    {
        loop {
            Op::push(self, n as usize);
            let i = f(&self, n as usize);
            if i > 1 || self.v[n as usize].c[i] == u32::MAX {
                break n;
            } else {
                n = self.v[n as usize].c[i];
            }
        }
    }

    fn access(&mut self, n: u32) {
        self.splay(n);
        self.v[n as usize].c[1] = u32::MAX;
        while self.v[n as usize].p != u32::MAX {
            let p = self.v[n as usize].p;
            self.splay(p);
            self.v[p as usize].c[1] = n;
            self.splay(n);
        }
    }

    fn link(&mut self, p: u32, c: u32) {
        self.access(c);
        self.access(p);
        self.v[c as usize].c[0] = p;
        self.v[p as usize].p = c;
    }
}