LCA

最小共通祖先のこと。

木上のある2つの頂点の最小共通祖先とは、ある頂点の部分木に2つの頂点がどちらも含まれるような頂点のうち、2つの頂点に一番近いもの（根から一番遠いもの）。

これを使って木上の2点間の距離などを高速に求めることができる。

code:cpp

struct Tree {

template <class Semigroup> class disjoint_sparse_table {

public:

using value_structure = Semigroup;

using value_type = typename value_structure::value_type;

private:

using container_type = ::std::vector<::std::vector<value_type>>;

public:

using const_reference = typename container_type::value_type::const_reference;

using size_type = typename container_type::value_type::size_type;

protected:

static size_type msb(size_type c) {

return 31 - __builtin_clz(c);

::std::size_t ret = 0;

if (c >> 16)

c >>= 16, ret += 16;

if (c >> 8)

c >>= 8, ret += 8;

if (c >> 4)

c >>= 4, ret += 4;

if (c >> 2)

c >>= 2, ret += 2;

return ret + (c >> 1);

}

container_type table;

public:

disjoint_sparse_table() : table() {}

template <class InputIterator>

disjoint_sparse_table(InputIterator first, InputIterator last) : table() {

table.emplace_back(first, last);

const size_type size = table.front().size();

for (size_type i = 2; i < size; i <<= 1) {

typename container_type::value_type v;

v.reserve(size);

for(size_type j = i; j < size; j += i << 1) {

for (size_type k = 2; k <= i; ++k)

for (size_type k = 1; k < i && j + k < size; ++k)

}

table.emplace_back(::std::move(v));

}

}

size_type size() const { return table.empty() ? 0 : table.front().size(); }

bool empty() const { return size() == 0; }

value_type fold_closed(const size_type first, const size_type last) const {

assert(first <= last);

assert(last < size());

if (first == last) {

} else {

const size_type p = msb(first ^ last);

return value_structure::operation(

}

}

const_reference operator[](const size_type index) const {

assert(index < size());

}

};

template <class T> class min_semigroup {

public:

using value_type = T;

static value_type operation(const value_type &x, const value_type &y) {

return ::std::min(x, y);

}

};

disjoint_sparse_table<min_semigroup<pair<int,int>>>dst;

vector<pair<int,int>>eular_tour;

vector<int>fa;

int n;

vector<vector<int>>g;

vector<int>dist_from_root;

//初期化

Tree(){}

Tree(int siz){

n = siz;

g.resize(n);

fa.resize(n);

dist_from_root.resize(n);

}

//辺を追加（無向辺）

void add_edge(int u,int v){

}

void init(int pos = 0,int pr = -1,int depth = 0){

eular_tour.push_back({depth,pos});

if(to==pr)continue;

init(to,pos,depth+1);

eular_tour.push_back({depth,pos});

}

if(pos==0){

dst = disjoint_sparse_table<min_semigroup<pair<int,int>>>(eular_tour.begin(),eular_tour.end());

}

}

int lca(int u,int v){

}

int dist(int u,int v){

}

};