Link-Cut 木

link_cut_tree.h

#pragma once

#include <vector>
#include <list>

// Link-Cut 木

template<class T=int> class link_cut_tree {
public:
	struct node;

	// 頂点数ははじめに決めておく. 辺はあとで追加する.
	link_cut_tree(int V = 1024*1024) : _vs(V) {}

	// 頂点はg.v(1)のような感じで参照. 辺は見ちゃダメ.
	node &v(int i) { splay(i); return _vs[i]; };
	node &parent(int i) { return _vs[_vs[i].parent_idx]; }
	node &left(int i) { return _vs[_vs[i].l_idx]; }
	node &right(int i) { return _vs[_vs[i].r_idx]; }
	bool is_root(int i) { return _vs[i].parent_idx < 0 || (_vs[_vs[i].parent_idx].l_idx!=i && _vs[_vs[i].parent_idx].r_idx!=i); }
	bool is_leaf(int i) { return _vs[i].l_idx<0 && _vs[i].r_idx<0; }
	
	// 点を追加する
	int add(T data, int parent=-1) { _vs.push_back(node{data,parent}); return _vs.size()-1; }
	// vcをvpの右要素にする.
	void addr(int vp, int vc) { _vs[vp].r_idx = vc; _vs[vc].parent_idx = vp; }
	// vcをvpの左要素にする.
	void addl(int vp, int vc) { _vs[vp].l_idx = vc; _vs[vc].parent_idx = vp; }
	// vをrootとして回転
	int rotr(int v) {
		if(_vs[v].l_idx<0) return v;
		const int l=_vs[v].l_idx;
		_vs[l].r_idx = v;
		_vs[l].parent_idx = _vs[v].parent_idx;
		_vs[v].parent_idx = l;
		_vs[v].l_idx = _vs[l].r_idx;
		return l;
	}
	int rotl(int v) {
		if(_vs[v].r_idx<0) return v;
		const int r=_vs[v].r_idx;
		_vs[r].l_idx = v;
		_vs[r].parent_idx = _vs[v].parent_idx;
		_vs[v].parent_idx = r;
		_vs[v].r_idx = _vs[r].l_idx;
		return r;
	}
	void revert(int x) {
		swap(_vs[x].l_idx, _vs[x].r_idx);
		if(_vs[x].l_idx>=0) revert(_vs[x].l_idx);
		if(_vs[x].r_idx>=0) revert(_vs[x].r_idx);
	}
	// スプレー
	void splay(int v) {
		while(!is_root(v)) {
			const int p = _vs[v].parent_idx;
			if(is_root(p)) {
				if(_vs[p].l_idx==v) rotr(p);
				else if(_vs[p].r_idx==v) rotl(p);
			} else {
				const int pp = _vs[p].parent_idx;
				if(_vs[pp].l_idx==p) {
					if(_vs[p].l_idx==v) {
						rotr(pp); rotr(p);
					} else if(_vs[p].r_idx==v) {
						rotr(pp); rotl(p);
					}
				} else if(_vs[pp].r_idx==p) {
					if(_vs[p].l_idx==v) {
						rotl(pp); rotr(p);
					} else if(_vs[p].r_idx==v) {
						rotl(pp); rotl(p);
					}
				}
			}
		}
	}
	//
	void expose(int x) {
		int r = -1;
		for(int i=x;i>=0;i=_vs[i].parent_idx) {
			splay(i);
			_vs[i].r_idx = r;
			r = i;
		}
		splay(x);
	}
	void link(int x, int p) {
		expose(x); expose(p);
		_vs[x].parent_idx = p;
		_vs[p].r_idx = x;
	}
	void cut(int x) {
		expose(x);
		const int l =_vs[x].l_idx;
		_vs[l].parent_idx = -1;
		_vs[x].l_idx = -1;
	}
	void evert(int x) {
		expose(x);
		revert(x);
	}
private:
	std::vector<node> _vs;
};

template<class T>
struct link_cut_tree<T>::node {
	T data;
	int parent_idx=-1;
	int l_idx=-1, r_idx=-1;
};