子がたくさんある木っぽい構造

tree.h

#pragma once

#include <vector>
#include <list>

// 子の数がたくさんあっても大丈夫な木
// 再配置もきっと怖くない

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

	// 頂点数ははじめに決めておく. 辺はあとで追加する.
	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]; }
	std::vector<node &> children(int i) {
		std::vector<node &> v;
		for(auto i: _vs[i].children_idx) v.push_back(i);
		return v;
	}
	bool is_root(int i) { return _vs[i].parent_idx < 0; }
	bool is_leaf(int i) { return _vs[i].l_idx<0 && _vs[i].r_idx<0; }
	
	// vcをvpの子にする.
	void add(int vp, int vc) {
		_vs[vp].children_idx.push_back(vc);
		_vs[vc].parent_idx = vp;
	}
	
private:
	std::vector<node> _vs;
};

template<class T>
struct tree<T>::node {
	T data;
	int parent_idx=-1;
	std::list<int> children_idx;
};